[백준 19582번] [그리디] 200년간 폐관수련했더니 PS 최강자가 된 건에 대하여

상당히 애먹은 문제이다...

 

전체적인 접근 방법은 다음과 같다.

1. 순차적으로 기존 상금의 합과 상금 상한을 비교한다.

2. 만약 상금의 합이 상금 상한을 넘는다는 의미는 해당 경기를 포기하거나, 적어도 앞의 경기 중 하나를 포기해야한다는 의미이다.
(즉, 이 지점을 기준으로 적어도 앞 부분에 1개의 시합을 포기해야한다는 의미와 동치이다.)

3. 이때, 상금의 합이 작을 수록 유리하다. 그러면 1개의 상금을 포기한다면 최대한 상금이 큰 것을 포기하는 것이 유리할 것이다. 단, 해당 경기를 포기하였을 때, 상금 상한을 넘을 수 있는지를 체크해서 가능해야 한다.

즉, 이 과정을 수행하기 위해 판단 당시에 위치한 대회의 상금의 값과 이전까지의 상금들 중 최댓값을 비교해서
만약 해당 대회의 상금의 값이 크면 그냥 그 대회를 포기하는 것이 낫고
더 작으면 이전까지의 상금들 중 최댓값을 지웠을 때 판단 당시 위치한 대회의 상금 상한을 넘지않는지를 체크해주면 된다.
(어차피 최댓값을 지웠을 때 상금 상한을 넘으면 어차피 나머지 아무거나 지워도 상금 상한을 넘게 된다.)

전체적으로 보면 각 시점에서 Optimal한 선택을 취하므로 탐욕적 선택 속성(Greedy choice property)를 지닌다고 볼 수 있다.

다만, 상금 상한 때문에 중간에 한번 끊고 진행해야 한다는 차이점이 존재한다. 

#include <iostream>
#include <vector>
#include <algorithm>

using namespace std;

int contest_num;

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

    cin >> contest_num;

    // 넘는 순간이 오면?(그거 전까지 최소 1개는 out)

    int index_check = contest_num;
    long long prize_sum_store = 0;

    long long max_value_store = - 1;

    for(int i = 0; i< contest_num; i++){
        long long limit_num, prize;
        cin >> limit_num >> prize;

        // 상한 초과
        if(prize_sum_store > limit_num){
            index_check = i + 1;

            if(max_value_store > prize){
                if(max_value_store >= prize_sum_store - limit_num){
                    prize_sum_store = prize_sum_store - max_value_store + prize;
                }
            }
            break;
        }
        // 넘지 않는 경우
        prize_sum_store += prize;
        max_value_store = max(max_value_store, prize);
    }

    for(int i = index_check; i < contest_num; i++){
        long long limit_num, prize;
        cin >> limit_num >> prize;

        if(prize_sum_store > limit_num){
            cout << "Zzz\n";
            return 0;
        }
        else{
            prize_sum_store += prize;
        }
    }

    cout << "Kkeo-eok\n";
    return 0;
}

특히, 최댓값만을 기준으로 판단하면 된다는 내용이 직관적으로 잘 와닿지 않으므로 반복해서 생각하도록 하자.