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

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

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

문제

2220년에도 “2220 신촌지역 대학생 프로그래밍 대회 동아리 연합 수시 대회”가 성공적으로 개최된다. SUAPC은 이제 모든 학생이 즐길 수 있도록 다양한 난이도의 대회가 1년에 수시로 열리며, 상금 규모는 억대가 되었다. 이런 미래를 예측한 연두는 냉동인간이 되어 폐관수련을 통해 알고리즘만 공부하였으며, 이제 모든 대회에서 반드시 1등을 한다.

하지만 각 대회마다 참가자격이 생겨 모든 대회에 참가하지 못할 수도 있다! 상금의 독식을 막기 위해 대회마다 “상금 상한”이 존재하며, 어떤 대회를 참가하기 전까지 모은 상금의 합이 그 대회의 상금 상한을 초과한다면 그 대회는 참가할 수 없다. 대회가 열리는 순서는 정해져 있고 대회들의 시간은 겹치지 않는다.

올해 열리는 N개의 대회에 모두 참가하여 상금을 쓸어 모을 계획을 세웠던 연두는 이 사실을 알고 큰 충격을 받았다. 대회를 하나까지 참가하지 못하는 것은 참을 수 있지만, 2개 이상의 대회를 참가할 수 없다면 절망에 빠져 500년을 더 냉동인간 상태로 지낼 것이다. 아직 손이 덜 해동된 연두를 위하여, 올해 연두가 적어도 N-1개의 대회에 참가할 수 있는지 여러분이 대신 확인해주자.

입력

첫 번째 줄에 올해 열리는 대회의 수 N이 주어진다. (1 ≤ N ≤ 100,000)

다음 N개의 줄에 i번째 대회에 대한 정보인 정수 xi, pi가 대회가 열리는 순서대로 주어진다. (1 ≤ xi, pi ≤ 109). 이는 i번째 대회에 참가하기 전까지 모은 상금의 합이 xi원 이하여야 이 대회에 참가할 수 있고, 이 대회에 참가하면 연두가 얻는 상금이 pi원임을 의미한다.

출력

만약 올해 연두가 최소 N − 1개의 대회에 참가할 수 있으면 Kkeo-eok을, 참가할 수 없으면 Zzz를 출력한다.

---

풀이

1. 해당 대회에 참여 할 수 있다면 상금을 누적 상금에 더해준다.
2. 해당 대회 참여 할 수 없다면 일단 여태까지 참여한 대회 중 최대 상금을 뺀다.
3. 최대 상금을 뺏음에도 대회에 참여 할 수 없거나 현재 참여하는 대회 상금이 최대 상금이라면 현재 대회를 스킵한다.

---

코드

#include <string>
#include <stdio.h>
#include <math.h>
#include <iostream>
#include <vector>
#include <algorithm>
#include <map>
#include <queue>
#include <stack>
#include <climits>

#define SWAP(a, b, type) do { \
    type temp; \
    temp = a;  \
    a = b;     \
    b = temp;  \
} while (0)

#define INF 1000000000
#define endl '\n'
#define ll long long

using namespace std;

ll N;
ll arr[100000][2];

void input() {
    cin>>N;
    for(int i=0;i<N;i++){
        cin>>arr[i][0]>>arr[i][1];
    }
}

void init() {
}


void solution() {
    ll sum=0; // 누적 상금
    ll limit;
    ll m=0;
    bool flag=false;  // 대회를 건너 뛴적이 있는지 없는지 확인
    
    
    for(int i=0;i<N;i++){
        limit=arr[i][0];

        if(limit>=sum){ // 대회에 참여할 수 있는 경우 상금을 더한다.
            sum+=arr[i][1];
            m=max(m,arr[i][1]);
        }else{
            
            if(!flag){ // 한 번도 대회를 건너 뛴적이 없다면 여태까지 최대 상금을 뺀다.
                sum-=m;
                flag=true;
            }else{
                // 건너 뛴 적이 있다면 Zzz 출력
                cout<<"Zzz";
                return;
            }
            
            if(limit<sum||m<arr[i][1]){ // 이전게 아니라 현재 대회 건너뜀
                sum+=m;
            }else sum+=arr[i][1];
    
        }
        
    }
    
    cout<<"Kkeo-eok";
}

int main()
{
    ios::sync_with_stdio(0); cin.tie(0); cout.tie(0);
    input();
    solution();
    return 0;
}