[BOJ]백준 22953번: 도도의 음식 준비(Python)/Backtracking, BinarySearch

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

22953번: 도도의 음식 준비

입국심사에서 백트래킹을 이용한 조합을 추가한 문제 ❗

격려의 최대 회수가 5이기 때문에 격려해줄 수 있는 모든 경우를 시뮬레이션 한 뒤 이진탐색으로 값을 구해주면 된당

import sys

input=sys.stdin.readline

n,k,c=map(int,input().split())
a=list(map(int,input().split()))
s=sum(a)-len(a)

def comb(idx, dep):
  global a, k, s

  if dep==c or dep>=s:
    left=0
    right=10**12
    while left+1<right:
      mid=(left+right)//2
      cnt=0

      for x in a:
        cnt+=mid//x

      if cnt>=k: right=mid
      else: left=mid

    return right

  ans=10**12
  for i in range(idx, len(a)):
    if a[i]==1:continue

    a[i]-=1
    ans=min(ans,comb(i, dep+1))
    a[i]+=1

  return ans

print(comb(0, 0))