[백준 / C++] 공주님의 정원 (골드3, 2457)

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

문제

오늘은 공주님이 태어난 경사스러운 날이다. 왕은 이 날을 기념하기 위해 늘 꽃이 피어있는 작은 정원을 만들기로 결정했다.

총 N개의 꽃이 있는 데, 꽃은 모두 같은 해에 피어서 같은 해에 진다. 하나의 꽃은 피는 날과 지는 날이 정해져 있다. 예를 들어, 5월 8일 피어서 6월 13일 지는 꽃은 5월 8일부터 6월 12일까지는 꽃이 피어 있고, 6월 13일을 포함하여 이후로는 꽃을 볼 수 없다는 의미이다. (올해는 4, 6, 9, 11월은 30일까지 있고, 1, 3, 5, 7, 8, 10, 12월은 31일까지 있으며, 2월은 28일까지만 있다.)

이러한 N개의 꽃들 중에서 다음의 두 조건을 만족하는 꽃들을 선택하고 싶다.

1. 공주가 가장 좋아하는 계절인 3월 1일부터 11월 30일까지 매일 꽃이 한 가지 이상 피어 있도록 한다.
2. 정원이 넓지 않으므로 정원에 심는 꽃들의 수를 가능한 적게 한다. 

N개의 꽃들 중에서 위의 두 조건을 만족하는, 즉 3월 1일부터 11월 30일까지 매일 꽃이 한 가지 이상 피어 있도록 꽃들을 선택할 때, 선택한 꽃들의 최소 개수를 출력하는 프로그램을 작성하시오. 

입력

첫째 줄에는 꽃들의 총 개수 N (1 ≤ N ≤ 100,000)이 주어진다. 다음 N개의 줄에는 각 꽃이 피는 날짜와 지는 날짜가 주어진다. 하나의 날짜는 월과 일을 나타내는 두 숫자로 표현된다. 예를 들어서, 3 8 7 31은 꽃이 3월 8일에 피어서 7월 31일에 진다는 것을 나타낸다. 

출력

첫째 줄에 선택한 꽃들의 최소 개수를 출력한다. 만약 두 조건을 만족하는 꽃들을 선택할 수 없다면 0을 출력한다.

예제 입력 1

4
1 1 5 31
1 1 6 30
5 15 8 31
6 10 12 10

예제 출력 1

2

예제 입력 2

10
2 15 3 23
4 12 6 5
5 2 5 31
9 14 12 24
6 15 9 3
6 3 6 15
2 28 4 25
6 15 9 27
10 5 12 31
7 14 9 1

예제 출력 2

5

---

문제 풀이

이번 문제는 3월 1일부터 11월 30일까지 매일 한 가지 이상의 꽃이 피어있도록 꽃들을 선택할 때 필요한 최소 꽃의 개수를 구해야 하는 문제입니다.

 

문제에서 꽃은 최대 100,000개까지 주어질 수 있습니다. 모든 경우의 수를 전부 탐색하는 것은 비효율적이므로, 그리디 알고리즘을 적용해 최적의 방법을 찾아야 합니다.

 

핵심 아이디어는 현재 꽃이 지기 전에 새로 피는 꽃들 중에서 가장 늦게 지는 꽃을 선택하는 것입니다.

 

풀이 과정은 다음과 같습니다:

1. 날짜 비교를 간편하게 하기 위해, 시작/종료 날짜를 "월/일" 형식에서 "일" 형식으로 변환합니다.
2. 꽃들이 피는 순서대로 정렬합니다.
3. 3월 1일 이전에 피고 가장 늦게 지는 꽃을 선택합니다.
4. 이전 꽃이 지기 전에 피면서, 가장 늦게 지는 다음 꽃을 선택합니다.
5. 3~4의 과정을 반복해 종료일이 11월 30일을 넘어가는 꽃이 나올 때까지 진행합니다.

코드

#include <iostream>
#include <queue>

using namespace std;

struct Comp
{
    bool operator()(const pair<int, int>& p1, const pair<int, int>& p2)
    {
        // 시작일이 같은 경우
        if (p1.first == p2.first)
        {
            // 종료일이 더 늦은 순으로 정렬
            return p1.second > p2.second;
        }
        else
        {
            // 시작일이 더 빠른 순으로 정렬
            return p1.first > p2.first;
        }
    }
};

int n;
priority_queue<pair<int, int>, vector<pair<int, int>>, Comp> pq;
// 월별 날짜 합계       1   2   3   4   5   6   7   8   9  10  11  12 
int sumArr[14] = { 0, 0, 31, 28, 31, 30, 31, 30, 31, 31, 30, 31, 30, 31 };
// 최소 개수 카운트
int cnt;
// 성공 실패 판별용 변수
int firstPos;
int endPos;

void Go()
{
    if (pq.empty()) return;

    // 첫번째 꽃을 꺼내줍니다.
    pair<int, int> flower = pq.top();
    pq.pop();

    while (!pq.empty())
    {
        pair<int, int> nextFlower = pq.top();

        // 만약 3월 1일 이전인 경우
        if (nextFlower.first <= sumArr[3] + 1)
        {
            // 만약 종료일이 flower보다 큰 경우
            if (nextFlower.second > flower.second)
            {
                // 시작 꽃 업데이트
                flower = nextFlower;
                pq.pop();
            }
            else
            {
                pq.pop();
            }
        }
        else
        {
            break;
        }
    }

    // 위치를 저장하고 수 증가
    firstPos = flower.first;
    endPos = flower.second;
    cnt++;

    while (!pq.empty())
    {
        if (endPos >= sumArr[12] + 1)
        {
            break;
        }

        // 다음 꽃 꺼내기
        pair<int, int> nextFlower = pq.top();
        pq.pop();

        // 만약 이전 꽃의 종료일보다 늦게 피는 경우라면 종료
        if (flower.second < nextFlower.first) break;

        // 이후 꽃들을 체크하며 올 수 있는 가장 늦게 피는 꽃 찾기
        // * 꽃 목록이 비어있는지 체크
        while (!pq.empty())
        {
            // * flower의 second보다 first가 작은지(이전에 피는지) 체크
            if (flower.second >= pq.top().first)
            {
                // * nextFlower의 second보다 다음 꽃의 second가 더 큰 경우(늦게 지는 경우) 
                if (nextFlower.second < pq.top().second)
                {
                    // * nextFlower 업데이트
                    nextFlower = pq.top();
                    // * 해당 꽃 목록에서 제거
                    pq.pop();
                }
                // 아닌 경우 종료
                else
                {
                    // * 해당 꽃 목록에서 제거
                    pq.pop();
                }
            }
            // 아닌 경우 종료
            else
            {
                break;
            }
        }

        // 꽃을 찾았으므로 카운트를 증가시키고, 최종 위치 업데이트
        cnt++;
        endPos = nextFlower.second;
        // 이전 꽃 업데이트
        flower = nextFlower;
    }
}

int main()
{
    // 날짜 연산
    for (int i = 1; i < 14; i++)
    {
        sumArr[i] = sumArr[i - 1] + sumArr[i];
    }

    cin >> n;

    for (int i = 0; i < n; i++)
    {
        int a, b, c, d;
        cin >> a >> b >> c >> d;

        // 날짜로 전부 치환
        int startDay = sumArr[a] + b;
        int endDay = sumArr[c] + d;

        // 만약 종료 날짜가 3월 1일보다 이전인 경우
        if (endDay <= sumArr[3] + 1)
        {
            // 해당 꽃은 절대 사용되지 않으므로 우선순위 큐에서 제외합니다.
            continue;
        }
        // 만약 시작 날짜가 12월 1일보다 이후인 경우
        if (startDay >= sumArr[12] + 1)
        {
            // 해당 꽃은 절대 사용되지 않으므로 우선순위 큐에서 제외합니다.
            continue;
        }

        pq.push(make_pair(startDay, endDay));
    }
    
    Go();

    if (firstPos <= sumArr[3] + 1 && endPos >= sumArr[12] + 1)
    {
        cout << cnt;
    }
    else
    {
        cout << 0;
    }
}

많이 어렵지는 않았지만, 다음 꽃을 구해주는 부분에서 else 쪽에 pop()을 해주는 것을 까먹어서,, 오래 찾았던 문제였습니다.