[boj] 백준 22953 도도의 음식준비 python 풀이

문제

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

 

문제 풀이

이분탐색, 백트래킹, 코드의 주석 참조

 

코드

import sys
input = sys.stdin.readline

N, K, C = map(int,input().split())
A_list = list(map(int,input().split()))
#격려를 요리 중에 하는게 아니고 최초에 1회만 함

def food_cnt(t_list, t):
    #t초에 만들 수 있는 요리의 갯수
    total = 0
    for i in range(len(t_list)):
        total += t//t_list[i]

    return total

def total_time(t_list, K):
    #K개의 요리를 하는데 A_list[i]가 몇번씩 반복되는가
    #완전탐색 불가 A_list[i]<=백만
    #이분탐색 ㄱㄱ
    #찾아야 되는 수 : 최소 조리 시간 t초
    #구하는 법 : t초에 만들 수 있는 요리의 갯수를 구해 K와 비교해가며 최소가 되는 t를 찾음
    s = 1
    e = max(t_list)*K*N # 요리 K를 모두 만드는데 걸릴 수 있는 최대시간

    while s<=e:
        mid = (s+e)//2

        total_cnt = food_cnt(t_list, mid)
        if total_cnt >= K:
            e = mid - 1
        else:
            s = mid + 1
        
    return s   
    
MIN = sys.maxsize
def back(left_C, idx):
    # 모든 경우의 수 탐색 : C가 작아서 가능할듯
    global MIN
    MIN = min(MIN, total_time(A_list, K))
    if left_C==0 or sum(A_list) == len(A_list): # 다 줄였거다 더 줄일 수 없을 때
        return
    
    for i in range(idx,N):
        if A_list[i] > 1:
            A_list[i] -= 1
            back(left_C-1,i)
            A_list[i] += 1

back(C,0)
print(MIN)