[백준 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)으로 구간을 줄여 성능에 별 차이도 없다.
Author And Source
이 문제에 관하여([백준 22953] 도도의 음식 준비 (Gold 5)), 우리는 이곳에서 더 많은 자료를 발견하고 링크를 클릭하여 보았다 https://velog.io/@daehoon12/백준-22953-도도의-음식-준비저자 귀속: 원작자 정보가 원작자 URL에 포함되어 있으며 저작권은 원작자 소유입니다.
우수한 개발자 콘텐츠 발견에 전념 (Collection and Share based on the CC Protocol.)