[C++]백준(BOJ) - 2457 공주님의 정원(그리디)

 

난이도 : 골III

알고리즘 유형 : 그리디 알고리즘

풀이 방법 : 정렬, 그리디

 

문제 경로

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

 

 

문제의 예시

오늘은 공주님이 태어난 경사스러운 날이다.

왕은 이 날을 기념하기 위해 늘 꽃이 피어있는 작은 정원을 만들기로 결정했다.

 

총 N개의 꽃

-> N (1 ≤ N ≤ 100,000)

모두 같은 해에 피어서 같은 해에 짐
하나의 꽃은 피는 날과 지는 날이 정해져 있다.

 -> Start 와 End 가 있음

  
5월 8일 피어서 6월 13일 지는 꽃은 5월 8일부터 6월 12일까지는 꽃이 피어 있고
6월 13일을 포함하여 이후로는 꽃을 볼 수 없다는 의미이다.

-> 6월 12일에 끝나면 13일에는 연결되지 않음

공주가 가장 좋아하는 계절인 3월 1일부터 11월 30일까지 
매일 꽃이 한 가지 이상 피어 있도록 한다.

정원이 넓지 않으므로 정원에 심는 꽃들의 수를 가능한 적게 한다.

 -> 그리디 알고리즘의 핵심

 

여기서 헷갈렸던 점은 날짜 파싱을 어떻게 하는가였다.

그 문제만 해결한다면 BOJ 1931 회의실 배정과 매우 비슷한 유형이였습니다.

날짜 파싱은 Month * 100 + Day를 통해 구현했으며, 이렇게된다면

3월 1일 -> 301, 11월 30일 -> 1130 같이 구분을 할 수 있게 됩니다.

 

마지막으로 정렬하여 start 값과 end 값을 갱신하며 정답을 찾을 수 있습니다.

아래는 C++ 코드입니다.

#include <iostream>
#include <vector>
#include <algorithm>

using namespace std;

int n;
vector<pair<int, int>> v;

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

    cin >> n;

    // 1 1 6 30
    // 60 10 12 10
    // 그리디 같음
    // 작은 것부터 큰 것으로 정렬해보자

    // 날짜 개념 파싱을 위해 100을 곱해주자.
    for (int i = 0; i < n; ++i)
    {
        int x, y, z, a; cin >> x >> y >> z >> a;
        int st = x * 100 + y;
        int en = z * 100 + a;

        v.push_back({st, en});
    }

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

    // 현재 시작점은 핀 꽃으로 하기 때문에 1로 초기화
    int cnt = 1;
    
    // 현재 가장 가까이 핀 꽃
    int cur_en = 301;
    // 현재 가장 멀리 핀 꽃
    int max_en = 301;

    for(const auto& [st, en] : v)
    {
        // 꽃이 이미 11월 30일 이상으로 피었다면
        if(max_en >= 1201) break;

        // 현재 핀 꽃의 시작 지점이 이전에 핀 꽃의 마지막 지점보다 크다면 갱신
        
        // ex) 예제 입력 1에서 
        // st(101) > cur_en(301) X
        // st(101) > cur_en(301) X
        // st(515) > cur_en(301) O
        // st(610) > cur_en(831) X
        if (st > cur_en)
        {
            cur_en = max_en;
            ++cnt;
        }
        
        
        // 갱신했는데도 크다면? 현재 핀 꽃의 맨 뒤보다 크다는 것
        // 즉, 꽃이 끊겼다는 것임
        
        // ex) 예제 입력이 
        // 2
        // 3 2 4 10
        // 4 20 5 10
        // 이라고 가정하면 
        // st(302) > cur_en(410)
        // st(420) > cur_en(410)
        
        if(st > cur_en)
        	break;
        
        // 현재 핀 꽃이 이전 핀 꽃보다 멀리있다면 갱신
        max_en = max(max_en, en);
           
    }

    // 12월 이상까지 도달하지 못했다면 중간에 끊김.
    if (max_en < 1201) cout << 0 << endl;
    else cout << cnt;

    return 0;
}