백준 12169번 Infinite House of Pancakes - C++(cpp) 풀이

 

---

 

1. 노말 턴보다 스페셜 턴을 먼저 진행하는 게 더 이득이다. 따라서 스페셜 턴을 먼저 다 진행한 후 뒤에 노말 턴을 몰아서 진행한다.
2. 총 i번의 노말 턴을 진행하는 경우, 스페셜 턴을 전부 진행한 뒤 다이너들의 접시에는 전부 i개 이하의 팬케이크가 남아있어야 한다.
3. 총 i(1 ≤ i ≤ 1000) 번의 노말 턴을 진행하는 모든 경우를 고려하여 최솟값을 찾는다.

 

1. 노말 턴보다 스페셜 턴을 먼저 진행하는 게 더 이득이다. 따라서 스페셜 턴을 먼저 다 진행한 후 뒤에 노말 턴을 몰아서 진행한다.

 노말 턴과 스페셜 턴을 한 번씩 진행해야 한다고 하자. 노말 턴 → 스페셜 턴의 순서로 진행할 때보다, 스페셜 턴 → 노말 턴의 순서로 진행할 때 같거나 더 적은 시간이 든다. 현재 다이너가 d명 있다면, 노말 턴을 먼저 진행하는 경우 d개의 팬케이크를 먹을 수 있다. 스페셜 턴을 먼저 진행해도 똑같이 d개의 팬케이크를 먹을 수 있고, 추가로 생긴 다이너의 팬케이크까지도 먹을 수 있다. 따라서 노말 턴보다 스페셜 턴을 먼저 진행해서 더 손해가 되는 경우는 없으므로, 스페셜 턴을 먼저 다 진행한 후 뒤에 노말 턴을 몰아서 진행해도 된다.

 

2. 총 i번의 노말 턴을 진행하는 경우, 스페셜 턴을 전부 진행한 뒤 다이너들의 접시에는 전부 i개 이하의 팬케이크가 남아있어야 한다.

 노말 턴을 전부 뒤로 몰기로 했으므로, 이제 몇 번의 노말 턴을 진행할 것인지를 정하자. 총 i번의 노말 턴을 진행하기로 하면, 노말 턴을 시작할 때 모든 다이너는 i개 이하의 팬케이크를 가지고 있어야 한다. 즉, 스페셜 턴으로 모든 다이너의 팬케이크를 i개 이하로 만들어주어야 한다. p개의 팬케이크를 가진 다이너는 최소 ceil(p/i) 개의 묶음으로 분할해야 하므로 ceil(p/i)-1명의 추가 다이너(스페셜 턴)가 필요하다. 따라서 필요한 총 스페셜 턴의 수는 모든 다이너에 대해 i개 이하로 쪼개기 위해서 필요한 스페셜 턴의 합이 되고, 전체 턴 수는 스페셜 턴 수 + 노말 턴 수(=i)가 된다.

 

3. 총 i(1 ≤ i ≤ 1000) 번의 노말 턴을 진행하는 모든 경우를 고려하여 최솟값을 찾는다.

 노말 턴으로만 진행해도 최대 1000번의 턴이면 모든 팬케이크를 먹어치울 수 있다. 따라서 i=1부터 1000까지 모든 경우를 진행하면서 최소 턴 수를 구하면 된다.

반응형

---

#include <iostream>
#include <string.h>

using namespace std;

int T, D, P;
int cnt[1001];

int solution(int d) {
    int ret = 1001;

    // 총 i번의 노말 턴을 진행하는 경우 시뮬레이션
    // 모든 경우의 수 시도 i=1~1000
    for (int i=1; i<=1000; i++) {
        // 노말 턴보다 스페셜 턴을 먼저 진행하는게 항상 이득이다.
        // 스페셜턴을 먼저 진행해야 노말 때 소진되는 팬케이크 수가 더 많아짐
        // 따라서 스페셜 턴을 먼저 다 진행한 후 노말턴 진행
        
        int special_cnt = 0;
        
        for (int p=1; p<=1000; p++) {
            // i번의 노말턴으로 끝내려면 전부 i이하여야 한다.
            // (p-1)/i = p개의 팬케이크를 i개 이하의 여러 묶음으로 나누기 위해 필요한 스페셜 턴 수
            special_cnt += cnt[p] * ((p - 1) / i);
        }
        
        ret = min(ret, special_cnt + i);
    }
    
    return ret;
}

void init_testcase() {
    memset(cnt, 0, sizeof(cnt));
}

int main()
{
    ios_base::sync_with_stdio(false);
    cin.tie(NULL); cout.tie(NULL);
    
    cin >> T;
    
    for (int t=1; t<=T; t++) {
        init_testcase();
        
        cin >> D;
        
        for (int i=0; i<D; i++) {
            cin >> P;
            cnt[P]++;
        }
        
        int ans = solution(D);
        
        cout << "Case #" << t << ": " << ans << "\n";
    }

    return 0;
}