BOJ :: 도도의 음식 준비 (no.22953)

문제

도도는 주방장이다. 총 K$K$개의 요리가 준비되는 최소 시간을 구해야 한다.

각각의 요리사는 자신만의 음식 조리 시간이 있다. 음식 조리 시간은 음식 하나를 만들 때 걸리는 시간이다.

도도는 요리사에게 격려를 해줄 수 있다. 격려받은 요리사는 영구적으로 음식 조리 시간이 1초 감소한다.

도도는 한 요리사에게 여러 번 격려할 수 있고, 요리사의 음식 조리 시간을 1초 미만으로 줄일 수는 없다.

도도를 위해 요리에 걸리는 최소 시간을 출력하는 프로그램을 만들어 보자.

입력

첫째 줄에 요리사의 수 N$N$ (1≤N≤10$1 \le N \le 10$), 만들어야 할 음식의 개수 K$K$ (1≤K≤1000000$1 \le K \le 1\,000\,000$), 격려해줄 수 있는 횟수 C$C$ (0≤C≤5$0 \le C \le 5$)가 주어진다.

둘째 줄에 길이가 N$N$인 정수 수열 A$A$가 주어진다. i$i$번째로 주어지는 수 Ai$A_i$는 i$i$번째 요리사의 음식 조리 시간이다. (1≤i≤N$1 \le i \le N$, 1≤Ai≤1000000$1 \le A_i \le 1\,000\,000$)

출력

첫째 줄에 K$K$개의 음식 조리가 완료되는 최소 시간을 출력한다.

생각

• 감이 잘 안 잡혀서 그리디로 접근을 했지만, 딱히 규칙이랄게 없었다.
• 결국 완전탐색으로 판단했다.
• 격려에 대한 경우의 수는 백트래킹 으로 구한 다음,
• 각 경우의 수에 대해 최소 시간을 구하여, 현재 결과값보다 작을 경우 갱신한다.

단, 최소 시간을 구하는 로직은 단순 완전 탐색은 불가능하다.
음식의 개수가 10^6 이기 때문에, O(n) 보다 빨라야 한다.

O(logn) 을 가진 이분탐색을 써야 한다는 결론이 나온다.

이분 탐색 조건
기준: 요리를 전부 처리하는 최소 시간
check: 해당 시간 안에 모든 요리 가능 여부

개인적으로 헤맸던 건, 습관적으로 무한을 10^9로 두었는데
이 문제의 경우 답이 1억 보다 커질 수 있다는 사실을 간과했다.

Solution

import sys
input = sys.stdin.readline

def isPossible(mid):
    cnt = 0
    for a in A:
        cnt += mid // a

    return K <= cnt

def binarySearch():
    left, right = 1, 1e13

    while left <= right:
        mid = (left + right) // 2
        if isPossible(mid):
            right = mid - 1
        else:
            left = mid + 1

    return int(left)


def dfs(idx, cnt):
    global ans
    ans = min(ans, binarySearch())

    if cnt == C: return

    for i in range(idx, N):
        if 1 < A[i]:
            A[i] -= 1
            dfs(i, cnt+1)
            A[i] += 1

N,K,C = map(int, input().split())
A = list(map(int, input().split()))

ans = 1e13
dfs(0,0)

print(ans)