Baekjoon 19582번 200년간 폐관수련했더니 PS 최강자가 된 건에 대하여

문제

https://www.acmicpc.net/problem/19582

걸린 시간

02 : 38 : 34 실패

풀이

C++

#include <bits/stdc++.h>
#define INF 987654321
using namespace std;

int main(){
    ios::sync_with_stdio(false);
    cin.tie(NULL);
    int n;
    cin >> n;
    int x, p, maxP = 0, absence = 0;
    long long reward = 0;
    for(int i = 0; i < n; i++){
        cin >> x >> p;
        if(reward <= x){
            reward += p;
            maxP = p > maxP ? p : maxP;
        }
        else if(reward-maxP > x || maxP < p){
            absence++;
        }
        else{
            reward -= maxP;
            reward += p;
            absence++;
        }
        if(absence == 2){
            cout << "Zzz" << "\n";
            return 0;
        }
    }
    cout << "Kkeo-eok" << "\n";
    return 0;
}

완전 탐색으로 풀이할 경우 n 개의 대회를 각각 한번씩 불참 n-1 할때의 경우를 모두 확인하기 때문에 복잡도는 O(n²)로 시간초과가 발생한다. 또 탐색의 경로가 모두 유일하므로 중복되는 부분이 없어 dp 도 적용할 수 없다. 이쯤 되면 greedy 한 방법으로 문제를 해결할 수 있지 않을까 싶어 최적해를 구할 수 있는 알고리즘을 생각해보기 시작했다.

하지만 올바른 알고리즘을 떠올려내지 못했고 검증 능력도 부족해 틀린 알고리즘을 오래 붙들고 있었다. 결국 답을 보게 되었는데 직접 손으로 테스트케이스를 풀어보면서 여러 아이디어를 떠올려내는 과정을 많이 연습해야겠다는 생각이 들었다. 풀이는 아래 블로그에 설명이 잘 되어 있다.

참고

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