[코드트리 챌린지] 5주차 - Parametric Search / 최소 통과 시간

https://www.codetree.ai/missions/8/problems/minimum-transit-time?&utm_source=clipboard&utm_medium=text 

코드트리 | 코딩테스트 준비를 위한 알고리즘 정석

문제 해결 방법

이 문제는 Parametric Search를 활용하여 해결할 수 있습니다. 주어진 시간 동안 각 통로가 얼마나 많은 물건을 통과시킬 수 있는지 계산하고, 그 합이 n개 이상인지 확인하는 것이 핵심입니다.

1. 결정 함수 (Decision Function)

먼저, 주어진 시간 mid 동안 n개의 물건을 모두 통과시킬 수 있는지를 판단하는 함수를 작성합니다. 이 함수는 각 통로가 mid 시간 동안 통과시킬 수 있는 물건의 개수를 계산하여 그 합이 n개 이상인지를 반환합니다.

2. Parametric Search

결정 함수를 활용하여 최소 시간을 찾아냅니다. 이진 탐색을 수행하면서 주어진 시간 mid 동안 n개의 물건을 모두 통과시킬 수 있는지 결정 함수를 통해 확인합니다.

# 결정 함수: 주어진 시간 mid 동안 n개의 물건을 모두 통과시킬 수 있는지 판단
def can_pass(mid, times, n):
    total = sum(mid // time for time in times)
    return total >= n

# Parametric Search를 수행하여 최소 시간을 찾아냄
def min_pass_time(n, m, times):
    left, right = 0, max(times) * n
    answer = right
    
    while left <= right:
        mid = (left + right) // 2
        if can_pass(mid, times, n):
            answer = mid
            right = mid - 1
        else:
            left = mid + 1
    return answer

# 입력 받기
n, m = map(int, input().split())
times = [int(input()) for _ in range(m)]

# 결과 출력
print(min_pass_time(n, m, times))

 

1. can_pass 함수는 각 통로가 주어진 시간 mid 동안 통과시킬 수 있는 물건의 개수를 계산하고, 그 합이 n개 이상인지를 판단합니다.
2. min_pass_time 함수에서는 이진 탐색을 수행하면서 can_pass 함수를 활용하여 최소 시간을 찾아냅니다.

지난 실력진단보다 점수가 다소 떨어진 걸 확인할 수 있다. 아무래도 심화 알고리즘에 대한 학습이 부족해서 그런 것으로 보인다. 

요즘 시험기간이라 좀 소홀하게 공부를 했던 것 같아 좀 더 공부를 해야겠다.