백준 22953

문제

풀이

각각의 요리가 준비되는 시간에서 1씩 빼는 모든 경우에서 T 시간이 걸렸을 경우 최소 K개의 요리가 조리되는 T의 최솟값을 구하는 문제이다.

우선 각각의 요리에서 1씩 빼는 모든 경우의 수를 구해야 하므로 요리사의 수 N, 격려 횟수 C일때 O(N^C)가 걸리게 된다.

이때 격려가 완료된 경우 K개의 요리가 준비되었는지 확인해야 된다.

이 경우를 구하는게 가장 고민이 됬는데, 1개의 요리를 만들고 조리시간이 10^6일때, 10^6개의 요리를 만드는 경우가 시간의 최악의 경우의 수가 된다. 그러므로 가장 오래 걸리는 시간은 10^12이다. 

가장 오래 걸리는 수를 hi, 0을 lo라 두고 이를 통해 매개변수 탐색을 하여 K개 이상의 요리를 만들 수 있는 최소 시간을 구했다.

코드를 참조할때 check가 K 이상일 경우 hi = mid를 했으므로 hi가 K 이상인 경우 최소 개수를 결국 만족하게 된다는게 포인트이다.

 

그러므로 총 시간복잡도는 O(N^C * log10^12 * N)이다.

 

#include <iostream>
using namespace std;
long long N, K, C, arr[11], ans = 1000000000001;
void solve(int c, int l) {
    if(c == 0) {
        long long lo = 0, hi = 1000000000000;
        while(lo+1 < hi) {
            long long mid = (lo+hi)/2;
            long long check = 0;
            for(int i=0; i<N; i++) {
                check += mid/arr[i];
            }
            if(check >= K) hi = mid;
            else lo = mid;
        }
        ans = min(ans, hi); 
        return;
    }
    for(int i=l; i<N; i++) {
        if(arr[i] == 1) {
            if(i == N-1) solve(0, i);
            continue;
        }
        arr[i] -= 1;
        solve(c-1, i);
        arr[i] += 1;
    }
}
int main() {
    cin>>N>>K>>C;
    for(int i=0; i<N; i++) cin>>arr[i];
    solve(C, 0);
    cout<<ans;
}

//3 6 0
//1 2 3
// 4