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개 이상을 만들 수 있는 시점을 찾아야 한다.
'문제풀이 > 백트래킹' 카테고리의 다른 글
[Javascript/자바스크립트] (프로그래머스) 양과 늑대 (0) | 2025.05.09 |
---|---|
[Javascript/자바스크립트] (프로그래머스) 불량 사용자 (0) | 2025.05.04 |
[Python/파이썬] 백준 14650번 걷다보니 신천역 삼 (Small) (0) | 2025.04.26 |
[Python/파이썬] 백준 2057번 팩토리얼 분해 (0) | 2025.04.07 |
[Python/파이썬] 백준 25369번 카드 숫자 곱을 최소로 만들기 (0) | 2025.04.02 |