백준[2457] 공주님의 정원

문제 설명

문제 링크

http://icpc.me/2457

2457번: 공주님의 정원

풀이

그리디로 풀 수 있다.

현재 가지고 있는 꽃이 죽기 전에 피고, 가장 오랫동안 살아있는 꽃을 고르면 된다.

날짜는 구현의 편의를 위해 달에 100을 곱하고 일을 더했다. ex) 2월 28일 = 228

문제를 읽자마자 그리디일거같았지만 구현하는데 시간이 꽤 걸렸다.

코드

#include <cstdio>
#include <algorithm>

using namespace std;
pair<int, int> arr[100005];

int main() {
    int n; scanf("%d", &n);
    for (int i = 0; i < n; i++) {
        int a, b, c, d; scanf("%d %d %d %d", &a, &b, &c, &d);
        arr[i] = {100 * a + b, 100 * c + d};
    }
    sort(arr, arr + n);
    int cur = 301, idx = 0, ans = 0, M = -1e9;
    while (cur <= 1130) {
        for (int i = idx; i < n; i++) {
            auto &[s, e] = arr[i];
            if (s > cur) break;
            if (e > M) {
                M = e;
                idx = i;
            }
        }
        if (M != cur) {
            cur = M;
            ans++;
        } else {
            printf("0");
            return 0;
        }
    }
    printf("%d", ans);
}