문제풀이/백트래킹

[Python/파이썬] 백준 22953번 도도의 음식 준비

딜레이레이 2025. 6. 2. 15:37

https://www.acmicpc.net/problem/22953

코드

n, k, c = map(int, input().split())
cooking_times = list(map(int, input().split()))

INF = int(1e12)
answer = INF


def total_cooking_time(arr, k):
    result = INF
    l, r = 1, INF
    while l <= r:
        mid = (l+r)//2

        count = 0
        for a in arr:
            count += mid//a
        if count < k:
            l = mid+1
        else:
            r = mid-1
            result = mid
    return result


def bt(idx, c):
    global answer
    if idx == n:
        answer = min(answer, total_cooking_time(cooking_times, k))
        return

    bt(idx+1, c)

    for encouragement in range(1, min(c+1, cooking_times[idx])):
        cooking_times[idx] -= encouragement
        bt(idx+1, c-encouragement)
        cooking_times[idx] += encouragement


cooking_times.sort()
start = 0
while start < n and cooking_times[start] == 1:
    start += 1
bt(start, c)
print(answer)

 

해당 문제를 풀기 위해서는 두 가지 알고리즘을 사용해야 했다.

 

- 백트래킹: 가능한 모든 격려 조합을 탐색하며 최적의 해를 찾는 데 사용

- 파라메트릭 서치: k개 이상의 요리를 만들 수 있는 최소 시간을 찾는 데 사용

 

좀 더 자세하게 말해보자면 다음과 같은 과정으로 진행했다.

백트래킹

각 셰프에게 c번의 격려를 나눠서 주는 모든 조합을 구해서, 각 조합으로 요리를 했을 때 K개의 요리를 만드는데 얼마나 걸리는지 구한다. 이 과정을 통해 가장 최소 시간이 걸리는 경우를 구한다.

 

이때 조리시간이 1인 요리사는 격려할 수 없기 때문에 처음 호출하기 전에 1인 경우는 `bt()` 재귀호출 과정에 포함되지 않도록 했다.

cooking_times.sort()
start = 0
while start < n and cooking_times[start] == 1:
    start += 1
bt(start, c)

 

파라메트릭 서치

N명의 셰프들이 하나의 요리를 완성하는 데 걸리는 시간이 담긴 배열 `arr`와 완성해야 하는 요리의 총 개수 `k`를 인자로 받는다. 파라메트릭 서치를 이용하여 최소 몇 초 후에 k개 이상의 요리를 완성할 수 있는지를 구한다.

 

이때 주의해야 할 점이 2가지 있다.

- 탐색 범위: 문제에 제시된 조건 상 최악의 경우에 답의 범위는 10^12까지 가능하다. 평소에 이 정도 큰 범위는 자주 나오지 않기 때문에 문제의 조건을 보고 범위를 잘 설정해야 한다.

- 조건: 정확히 K개의 요리를 완성하는 시간이 존재하지 않을 수도 있다. 그렇기 때문에 이분탐색처럼 정확히 K개의 요리를 완성하는 시점을 찾으면 안되고, K개 이상을 만들 수 있는 시점을 찾아야 한다.