BOJ 백준 22953번 도도의 음식 준비

 

BOJ 백준 22953 도도의 음식 준비

 

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

22953번: 도도의 음식 준비

 

 

K개의 요리를 조리하는 N명의 요리사의 조리시간이 주어진다. 한 요리사에게 격려를 여러 번 할 수 있고, 요리사에게 격려를 한 번 할 때마다 격려를 받은 요리사의 조리 시간은 1초 감소한다. 격려할 수 있는 최대 횟수가 C회일 때, K개의 요리를 조리하는 데 걸리는 최소 시간을 구해야 한다.

 

 

 

처음에는 Greedy(그리디) 알고리즘으로 해결하려고 했지만, 어떤 요리사에게 격려를 얼마나 하느냐에 따라 결과가 달라질 수 있어서 구현하기 어려울 것 같다고 느꼈다. 문제를 잘 관찰하면 N과 C의 값이 유난히 작은 것을 의심할 수 있는데, Brute Force(브루스 포스)를 사용하는 문제이지 않을까 하는 의심이 들었다.

 

 

 

Brute Force 방법으로 풀 수 있는지 확인하고자 시간 복잡도를 구했다. 요리사에게 격려할 수 있는 경우의수는 10의 0제곱부터 5제곱까지를 모두 더한 값이 나오는데, naive하게 10의 6승이라고 해도 백만이므로 값이 생각보다 크지 않음을 알 수 있다. 

 

 

 

K개를 요리하는 데 걸리는 최대 조리 시간은 K의 최댓값과 A의 최댓값을 곱한 값인데, 이를 고려해도 10의 12승이므로 이진 탐색을 고려하면 가능한 최소 요리 시간을 찾는데 그리 많은 시간이 걸리지 않음을 알 수 있다. log(10^12)는 약 40이므로 앞에서 구한 격려의 경우의 수 10의 6승에 40을 곱해도 주어진 제한 시간 내로 충분히 계산 가능하다.

 

 

 

즉, 격려 가능한 모든 경우마다 음식 조리를 완료할 수 있는 최소 시간을 이진 탐색으로 찾으면 가능하다. 코드를 보면 이해가 쉬울 것이다.

 

 

#include <cstdio>
#include <limits.h>
#include <algorithm>
using namespace std;
using ll = long long;

const int N_MAX = 10;
const ll T_MAX = (ll)1e12;

int n, c;
ll k, ans = T_MAX;
ll a[N_MAX + 1];

void findTime(){
    ll minTime = T_MAX;
    ll left = 1, right = T_MAX;
    while(left < right){
        ll mid = left + (right - left) / 2;
        ll food = 0;
        for (int i = 1; i <= n; i++){
            food += mid / a[i];
        }
        
        if (food >= k){
            minTime = mid;
            right = mid;
        }
        else {
            left = mid + 1;
        }
    }
    ans = min(ans, minTime);
    return;
}

void go(int cnt){
    
    findTime();
    
    // 격려 횟수 다 사용하면
    if (cnt == c){
        return;
    }
    
    for (int i = 1; i <= n; i++){
        if (a[i] - 1 > 0){
            a[i] -= 1;
            go(cnt + 1);
            a[i] += 1;
        }
    }
    
    return;
}

int main(){
    scanf("%d %lld %d", &n, &k, &c);
    
    for (int i = 1; i <= n; i++){
        scanf("%lld", &a[i]);
    }
    
    go(0);
    printf("%lld\n", ans);
    
    
    return 0;
}