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

✍️ 첫번째 접근

하루 종일 이 문제에 매달리면서 공주님과 데이트(?)하는 느낌이었다.
어쨌든, 문제를 읽으면서 월과 일을 단순하게 처리해야겠다는 생각이 들어 월에 100을 곱하고 이에 일을 더한 값으로 날짜를 쉽게 구분할 수 있게 하였다.
일단 입력받은 날짜들의 최솟값이 3월 1일 이하이거나 최댓값이 11월 30일 이하라면 0을 출력하게 하였다.
그리고 꽃이 지는 날짜를 기준으로 정렬하여 꽃이 지는 날짜보다 작거나 같은 꽃 중에서 꽃이 지는 날짜가 가장 큰 꽃을 택하는 과정을 구현하였다. 여기서 꽃이 지는 날짜를 기준으로 정렬하였을 때 가장 작은 상태일 경우는 꽃이 피는 날짜보다 작거나 같은 꽃 중에서 택하게 하였다. 아래의 그림은 문제에 있는 예제 입력1에 대한 풀이이다.

하지만 이렇게 하였을 경우, 서로 다른 꽃이 피는 날짜와 지는 날짜가 동일할 경우의 테스트케이스를 돌려보았을 때 그 날짜에는 꽃이 안피기 때문에 이에 대한 처리를 못하여 틀리게 되었다.

#include <bits/stdc++.h>
using namespace std;
int n;
pair<int,int> arr[100005];
int main(void) {
    ios::sync_with_stdio(0);
    cin.tie(0);

    cin >> n;

    int minValue = 1250, maxValue = 0;

    for(int i = 0; i < n; i++) {
        int s_m, s_d, e_m, e_d;
        cin >> s_m >> s_d >> e_m >> e_d;

        // 꽃이 지는 날짜를 기준으로 정렬하기 위해 second와 first의 순서를 바꿈
        // 월, 일 계산을 편하게 하기 위해 월에 해당하는 값에 100을 곱함
        arr[i].second = s_m*100 + s_d;
        arr[i].first = e_m*100 + e_d;

        if(maxValue < arr[i].first)
            maxValue = arr[i].first;
        if(minValue > arr[i].second) 
            minValue = arr[i].second;
    }

    // 두 조건을 만족하는 꽃들을 선택할 수 없다면 0을 출력
    if(minValue > 301 || maxValue <= 1130) {
        cout << 0;
        return 0;
    }

    // 꽃이 지는 날짜를 기준으로 정렬
    sort(arr,arr+n);

    int t = arr[0].second;
    int next_t = arr[0].first;
    int ans = 0;
    for(int i = 1; i < n; i++) {
        if(t >= 1201)
            break;
        int maxIndex = i;
        for(int j = i+1; j < n; j++) {
            if(arr[j].second >= 1201)
                break;
            if(arr[j].second <= t) {
                if(arr[j].first > next_t) {
                    maxIndex = j;
                }
            }
        }
        ++ans;
        i = maxIndex;
        t = arr[i].first;
        next_t = arr[i].second;
    }

    cout << ans;


    return 0;
}

✍️ 두번째 접근

어차피 3월 1일부터 11월 30일까지는 276일뿐이니 3월 1일부터 12월 1일이 되기 전까지 while문을 돌리고 현재 시점에서 피어있는 꽃 중에서 가장 마지막에 지는 꽃을 선택한다. 또한, 서로 다른 꽃이 피는 날짜와 지는 날짜가 겹치거나 그 차이가 있을 경우(여기서 차이의 예로는 A 꽃의 피는 날짜: 5/31, B 꽃의 지는 날짜: 5/30이다.)에 대한 예외를 처리해준다.

#include <bits/stdc++.h>
using namespace std;
int n;
pair<int,int> arr[100005];
int main(void) {
    ios::sync_with_stdio(0);
    cin.tie(0);

    cin >> n;

    int minValue = 1250, maxValue = 0;

    for(int i = 0; i < n; i++) {
        int s_m, s_d, e_m, e_d;
        cin >> s_m >> s_d >> e_m >> e_d;

        // 꽃이 지는 날짜를 기준으로 정렬하기 위해 second와 first의 순서를 바꿈
        // 월, 일 계산을 편하게 하기 위해 월에 해당하는 값에 100을 곱함
        arr[i].second = s_m*100 + s_d;
        arr[i].first = e_m*100 + e_d;

        if(maxValue < arr[i].first)
            maxValue = arr[i].first;
        if(minValue > arr[i].second) 
            minValue = arr[i].second;
    }

    // 두 조건을 만족하는 꽃들을 선택할 수 없다면 0을 출력
    if(minValue > 301 || maxValue <= 1130) {
        cout << 0;
        return 0;
    }

    // 꽃이 지는 날짜를 기준으로 정렬
    sort(arr,arr+n);

    int t = 301;
    int ans = 0;
    while(t < 1201) {
        int next_t = t;
        for(int i = 0; i < n; i++) {
            if(arr[i].second <= t && arr[i].first > next_t)
                next_t = arr[i].first;
        }
        // t에서 더 이상 전진이 불가능함 피는 날짜와 지는 날짜가 서로 맞닿아 있지 않기 때문
        if(next_t == t) {
            cout << 0;
            return 0;
        }
        ++ans;
        t = next_t;
    }

    cout << ans;


    return 0;
}