[백준 22953] 도도의 음식 준비 (Gold 5)

문제

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

접근

Backtracking과 Parametric Search로 문제를 접근.

1) 요리사를 격려할 수 있는 모든 경우를 구하기 위해 중복조합을 사용했다. 단 요리사의 음식 조리 시간이 1이면 격려 횟수만 증가 시키고 값은 그대로 유지한다.

2) 인자에 있는 cnt가 c와 같아지면 Parametric Search를 이용해 최적의 해를 구한다.

3) 아래 코드에서 mid는 음식 조리가 완료되는 시간. mid//요리사의 음식 조리 시간 == 요리사가 만들 수 있는 음식의 갯수이므로 이 값을 cnt에 더하고 k보다 크면 mid와 현재 answer 중 작은 값을 answer에 넣고, high의 범위를 줄여 mid를 작게 한다.

Code

import sys


def go(idx, cnt, length):
    if cnt == c:
        global answer
        low,high =1, 1000000*1000000*10
        while low <= high:
            mid = (low + high)//2
            cnt=0
            for arr in arrs:
                cnt += mid//arr
            if cnt >= k:
                answer = min(answer, mid)
                high = mid -1
            else:
                low = mid +1
        return

    for i in range(idx, length):
        if arrs[i] > 1:
            arrs[i] -=1
            go(i, cnt+1, length)
            arrs[i] +=1
        else:
            go(i, cnt + 1, length)

answer = 1000000*1000000*100

n,k,c = map(int,sys.stdin.readline().split())
arrs = list(map(int, sys.stdin.readline().split()))
arrs_len = len(arrs)
go(0, 0,arrs_len)
print(answer)
  

여담

high를 어느 값으로 줘야할지 몰라서 문제에서 나올 수 있는 가장 큰 값으로 줬다. 헷갈리는 경우 일단 가장 큰 값으로 주자. 어차피 O(logN)으로 구간을 줄여 성능에 별 차이도 없다.