백준 2457번 [공주님의 정원](C++) -yes6686- 티스토리

백준 문제 풀이: 2457 (공주님의 정원)

---

문제 링크: https://www.acmicpc.net/problem/2457

문제 설명:

공주님의 정원을 3월 1일부터 11월 30일까지 꽃이 한 송이 이상 피어 있게 하려면, 어떤 꽃들을 선택해야 하는지 찾는 문제입니다. 각 꽃은 피는 날짜와 지는 날짜가 주어지며, 최소한의 꽃을 선택해 정원을 끊김 없이 채워야 합니다.

그리디 알고리즘을 적용하여 구간을 선택하는 문제이며, 가장 긴 구간을 덮는 방식으로 다음 구간을 선택해야 합니다.

---

문제 해결 코드

// 공주님의 정원 (그리디 구간 선택)
#include <iostream>
#include <algorithm>
#include <queue>
using namespace std;

pair<int, int> arr[100001];
queue<pair<pair<int, int>, int>> q;
int marr[13];  // 월별 일수 저장

int main() {
    ios::sync_with_stdio(false);
    cin.tie(NULL);

    for (int i = 1; i <= 12; i++) {
        if (i == 4 || i == 6 || i == 9 || i == 11) marr[i] = 30;
        else if (i == 2) marr[i] = 28;
        else marr[i] = 31;
    }

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

        // 지는 날짜가 3/1 이전이면 무시
        if (c <= 2 || (c == 3 && d == 1)) {
            arr[i].first = 9999999;
            continue;
        }

        int start = 0, end = 0;
        for (int j = 1; j < a; j++) start += marr[j];
        start += b;
        for (int j = 1; j < c; j++) end += marr[j];
        end += (d - 1);
        arr[i] = {start, end};
    }

    int as = 0, ae = 0;
    for (int i = 1; i <= 2; i++) as += marr[i];
    as += 1;  // 3월 1일
    for (int i = 1; i <= 10; i++) ae += marr[i];
    ae += 30; // 11월 30일

    sort(arr, arr + n);

    int ans = 100001, si = 0, maxS = -1;

    for (int i = 0; i < n; i++) {
        if (arr[i].first <= as && arr[i].second >= as) {
            if (maxS <= arr[i].second) {
                maxS = arr[i].second;
                si = i;
            }
        }
    }

    if (maxS == -1) {
        cout << 0 << '\n';
        return 0;
    } else if (arr[si].second >= ae) {
        cout << 1 << '\n';
        return 0;
    }

    q.push({{arr[si].first, arr[si].second}, 1});
    for (int i = si + 1; i < n; i++) {
        if (arr[i].first == 9999999) break;

        while (!q.empty()) {
            auto [f, k] = q.front().first;
            int d = q.front().second;

            if (k + 1 < arr[i].first) {
                q.pop();  // 이어지지 않는 구간은 버림
            } else {
                if (arr[i].second >= ae) {
                    ans = min(ans, d + 1);
                    q.pop();
                    break;
                } else {
                    if (arr[i].second > k) {
                        if (f == arr[i].first) {
                            q.pop();
                            q.push({{arr[i].first, arr[i].second}, d});
                        } else {
                            q.push({{arr[i].first, arr[i].second}, d + 1});
                        }
                    }
                    break;
                }
            }
        }
    }

    cout << (ans == 100001 ? 0 : ans) << '\n';
}

---

코드 설명

• 핵심 알고리즘: 정렬 + 그리디 + 큐를 이용해 이어지는 가장 긴 구간을 선택합니다.
• 구현 세부사항:
  • 3월 1일 ~ 11월 30일 사이의 일자를 정수로 변환해 비교
  • 현재 구간에서 가장 멀리 갈 수 있는 구간을 선택
  • 큐를 사용해 다음으로 이어질 수 있는 꽃을 갱신하며 최소 횟수를 추적
• 시간 복잡도 분석: O(n log n) (정렬) + O(n) (탐색), 전체적으로 효율적

---

결과

정원을 3월 1일부터 11월 30일까지 끊김 없이 채울 수 있는 최소 꽃의 수를 출력합니다.

예시 입력:

5
2 28 3 5
3 4 5 10
4 15 9 10
6 10 9 30
10 20 11 30

예시 출력:

0

구간 선택 문제에서 전형적인 그리디 패턴을 보여주는 문제입니다. 다른 전략이 있다면 댓글로 공유해주세요!