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

사용한 알고리즘

그리디 알고리즘

알고리즘 설명

연속적으로 진행되는 N개에 대회에서 N-1 이상 참가하는 방법을 찾는 문제이다
순차적으로 대회에 참가하며 상금을 쌓아간다
여기서 1~K-1 까지 모든 대회를 참가하고, 이제 K번째 대회를 참가한다고 가정하자
K번째 대회에 참가하지 못하는 경우 경우의 수는 다음과 같다.
1. K번째 대회를 참가하지 않는다.
1. 1~K-1 중 한 대회를 참여하지 않고 현재 대회를 참가한다.
위 둘중 하나를 선택해야 하는데 이를 선택하는 것이 그리디 알고리즘 처럼 선택가능하다.
그리디한 접근은 1~K번째 대회 중 가장 높은 상금금액을 주는 경우를 제외하는 것이다.
- 1) K번째가 가장 높은 상금이면 K번째 대회를 스킵하면 된다.
- 2) 1~K-1 중 가장 높은 상금이 있다면 그 대회를 제외한 뒤 K번째 대회를 참여할 수 있는지 확인한다.
- 3) 1~K-1 중 가장 높은 상금이 있지만 그 대회를 제외한 뒤에도 K번째 대회를 참여할 수 없다면 K번째 대회를 참석하지 않는다.
대회는 한 번만 제외할 수 있기 때문에 flag를 두어서 이를 처리해준다.

풀이

#include <bits/stdc++.h>
using namespace std;
using ll = long long;

const int MAX_N=100001;

int N;
int arr[MAX_N], money[MAX_N];

int main() {
    scanf("%d", &N);
    for (int i=0; i<N; i++)
        scanf("%d%d", &arr[i], &money[i]);

    int flag = 1;
    int max_money = 0;
    ll cur_money = 0;
    int count = 0;

    for (int i=0; i<N; i++) {
        if (cur_money <= arr[i]) {
            count++;
            cur_money += money[i];
            max_money = max(max_money, money[i]);
        } else if (flag == 1) {
            flag = 0;
            // pop here
            if (max_money <= money[i]) continue;

            // pop maximum money
            cur_money -= max_money;
            if (cur_money <= arr[i]) cur_money += money[i];
            else cur_money += max_money;
        } else {
            break;
        }
    }
    puts((count >= N-1) ? "Kkeo-eok" : "Zzz");
    return 0;
}