[백준] 22953 도도의 음식 준비 (C++)

22953번: 도도의 음식 준비

 이번 여름 '신촌 알고리즘 연합 캠프 콘테스트 - 초급'에 나온 문제이다. 그 당시에 나는 이 문제를 풀지 못했었다. 문제에서 주방장이 요리사에게 격려하는 과정이 Greedy할 것이라고 생각해서 풀었기 때문이다. 격려를 한 뒤, 이분 탐색을 통해 최소 시간을 찾는 방식으로 문제를 풀었었고 당연히 틀렸다.

 

 

 대회가 끝나고 다시 문제를 보니 격려해줄 수 있는 횟수가 매우 작아서 브루트포스 기법을 이용해 가능한 모든 경우의 수대로 격려를 하고, 이분 탐색을 통해 최소 시간을 찾을 수 있을 것 같더라. 아래의 풀이가 이 방식이다.

 

 

 지금 이 문제를 보니까, 이번 신촌 연합 알고리즘 캠프에서 배운 브루트포스와 이분탐색을 배운 그대로 써먹어서 풀 수 있게 잘 만든 문제인 것 같다. 아래의 코드도 브루트포스, 이분탐색 숙제할 때 작성했던 코드를 붙여놓은 느낌이다.

 

---

풀이

 solve함수를 통해 문제를 해결한다. solve함수의 input은 C값이다.

 

 solve함수에서는 C가 양수이면 요리사의 시간을 1 줄이고, solve(C-1)을 호출한다. 그 후에는 방금 줄인 요리사의 시간을 다시 원상태로 돌려놓는다. 이 과정이 코드의 39~52번 째 줄이다.

 

 solve함수에서 C가 0이되면(=격려를 모두 완료하면) 이분탐색을 통해 최소 요리시간을 찾는다. mid값(음식 조리시간)일 때, K개 이상 만들 수 있는지 확인하는 possible함수를 이용하였다. mid값일 때, K개 이상 만드는 것이 가능하다면 그 시간보다 더 오래걸리는 시간은 모두 가능하기 때문에, high값을 mid-1로 바꾸어준다. 반면, mid값일 때, K개 이상 만드는 것이 불가능 하다면, 그 답은 그 mid값보다 크기 때문에, low값을 mid+1로 바꾸어주면서 풀었다. 여튼 그렇게 구한 최소 조리시간이 ans(답)보다 작다면 그 값이 ans(답)이다. 이 과정을 가능한 모든 경우만큼 실행하므로 올바른 답을 구할 수 있다.

 

 possible 함수에서는 각 요리사가 주어진 시간에 몇 개를 만드는지 정수 단위로 계산하여 모두 더해주었다. 그 값이 K이상이면 true를 반환한다. 아, 그리고 아래의 코드 15번 째 줄에서

sum += ll(sec / vec[i]); 가 아닌
sum += ll(sec / max(ll(1), vec[i])); 를 이용하였다.

그 이유는 vec[i] (i번 째 요리사의 음식 조리시간)가 1이하로 내려갈 수 없기 때문이다! 나는 이 부분을 놓쳐서 몇 번 틀렸었다. 이 부분을 놓치면 아래와 같은 반례들이 있다.

 

반례 2가지

3 3 1

1 1 1

 

3 3 2

1 2 1

---

코드

#include <iostream>
#include <bits/stdc++.h>
#define endl '\n'
#define INF 98760000000000
using namespace std;
using ll = long long;

ll n, k, c, a;
ll ans = INF;
vector<ll> vec; //요리사의 음식 조리 시간

bool possible(ll sec) { //음식 조리시간이 sec일 때, K개 이상 만들 수 있는지 확인하는 함수
    ll sum = 0; //총 만드는 음식의 갯수
    for (ll i = 0; i < vec.size(); i++) {
        sum += ll(sec / max(ll(1), vec[i])); //각 요리사는 초당 (1/vec[i])개를 만들 수 있음
    }
    if (sum >= k) return true;
    else return false;
}

void Binary_Search() { //시간 이분탐색
    ll low = 1, high = INF;
    ll mid = (low + high) / 2;
    ll tmp = INF;
    while (low <= high) {
        mid = (low + high) / 2;
        if (possible(mid)) { //음식조리시간이 mid일 때, K개 이상 만들 수 있다면
            tmp = min(tmp, mid);
            high = mid - 1;
        }
        else { //음식조리시간이 mid일 때, K개 이상 만들 수 없다면
            low = mid + 1;
        }
    }

    if (tmp < ans) ans = tmp; //이분탐색을 통해 찾은 값이 ans보다 작으면 그 값이 ans가 된다.
}

void solve(ll chance) { //브루트포스이용
    if (chance == 0) { //c값이 0이면 값 계산
        Binary_Search();
        return;
    }
    else {
        for (ll i = 0; i < vec.size(); i++) {

            vec[i]--; //격려 1번
            solve(chance - 1); //격려 1번했으니까 chance값 1 빼주기
            vec[i]++; //격려하기 전으로 되돌려 놓는 작업
        }
    }
}

int main() {
    ios::sync_with_stdio(false); cin.tie(NULL); cout.tie(NULL);

    cin >> n >> k >> c;

    for (ll i = 0; i < n; i++) {
        cin >> a;
        vec.push_back(a);
    }

    solve(c); //주어진 c값을 가지고 문제 해결

    cout << ans << endl; //답 출력

    return 0;
}