BOJ : 2457 공주님의 정원

---

[BOJ 2457(G4) 리뷰]

전형적인 그리디 문제라지만 나에겐 너무 어려웠다 ㅠ..
날짜를 저장하는 방식과 꽃을 선택하는 방식에 대해 이해는 했지만 막상 코드로 짜려니 막막했다.

알고리즘은 다음과 같다.
현재 날짜를 기준으로 현재 일보다 이전에 핀 꽃들중 가장 오랫동안 피는 꽃을 선택해야 한다.
공주는 3월1일부터 꽃이 피어있어야 한다 했으므로 3월1일을 기준으로 3월1일 이전에 핀 꽃들 중 가장 오랫동안 피는 꽃을 선택하면 된다. 예를들어 3월1일부터 6월3일까지 핀다면 다음 꽃은 6월3일 이전에 피는 꽃 중 가장 오랫동안 피는 꽃을 선택해야 한다.

위 알고리즘으로 11월 30일까지 꽃이 피어있도록 하고, 11월 30일이 지나면 반복문을 종료하고 정답을 출력하면 된다.
말로 설명하면 쉽지만 경계조건 등을 생각해줘야해서 조금 까다로웠다.

정답률이 낮은 문제는 항상 그만한 이유가 있는 것 같다.

---

/*
    20.09.06
    BOJ : 2457 공주님의 정원 (https://www.acmicpc.net/problem/2457)
    그리디
*/

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

vector <pair<int, int>> F;

int main(void) {
    ios::sync_with_stdio(0);
    cin.tie(0);

    int N;
    cin >> N;
    for (int i = 0; i < N; i++)
    {
        int s1, s2, e1, e2;
        cin >> s1 >> s2 >> e1 >> e2;
        F.push_back({ s1 * 100 + s2,e1 * 100 + e2 });
    }

    sort(F.begin(), F.end());

    int date = 301, idx = 0, maxdate = 0;
    int ans = 0;
    while (date <= 1130)
    {
        for (int i = idx; i < N; i++)
        {
            if (F[i].first > date) break;
            if (F[i].second > maxdate)
            {
                maxdate = F[i].second;
                idx = i;
            }
        }

        if (maxdate==date)
        {
            cout << 0;
            return 0;
        }
        else
        {
            date = maxdate;
            ans++;
        }
    }
    cout << ans;
        
}

엄청난 고생의 흔적.jpg