[c++] 백준 #2457 공주님의 정원 (190927)

< 풀이 >

Greedy 방법. 회의실 배정과 비슷하게 풀면 된다.

3월 1일부터 11월 30일까지 매일 꽃이 하루에 한 개 이상 펴 있도록 꽃들을 선택할 때 선택한 꽃의 최소 개수를 출력해야 한다. 최소의 꽃을 선택하려면, 시작 시점이 증가하는 순서대로 정렬하고, 시작시점이 같으면 끝 지점이 작은 걸 위에 올린다. 정렬된 결과 예시는 다음과 같다.

1 1 5 31

1 1 6 30

5 15 8 31

6 10 12 10

 

시작 시간이 31(3월 1일)~1130(11월 30일)까지 갈 수 있다. 맨 처음에 끝 시간은 31로 초기화를 한다. 시작 시간이 제일 작은 애들부터 업데이트했기 때문에 맨 처음 애의 시작시간이 31보다 커버리면 아예 불가능하기 때문.

시작 시간이 현재 끝 시간보다 작은 애들을 탐색해보고, 그 중에서 가장 큰 값을 next로 취한다 → 위의 예시에서 31보다 작은 애는 11이니까 531, 630 이렇게 끝 시간이 업데이트된다.

그러고 나서 다시 while문을 돌면 630보다 작은 애들 중에서 가장 큰 값을 next로 취한다. 그러면 최종적으로 1210으로 업데이트가 된다. 

시간 복잡도는 O(NlogN)이다. 문제 난이도 자체는 쉬우나, 경계값에서의 구현이 꼼꼼해야 한다. 1 1 11 30 이런 식으로 돼있으면11월 30일에는 꽃이 지기 때문에, 11 30일에 꽃이 펴있어야 한다는 걸 잘 생각해야 한다. (구간이 [a, b]이런 식으로 닫힌 구간이 아니라, [a, b) 이렇게 열려있는 구간이므로 주의.)

 

< 소스코드 >

#include <bits/stdc++.h>
using namespace std;
#define INF 987654321
typedef long long ll;
typedef pair<int, int> ii;
typedef tuple<int, int, int> iii;
#define pb push_back

int main(){
    ios::sync_with_stdio(false);
    cin.tie(0);
    int N; cin >> N;
    vector<ii> flower;
    for(int i=0; i<N;i++){
        int a, b, c, d; cin >> a >> b >> c >> d;
        int start = 100 * a + b;
        int end = 100 * c + d;
        flower.pb({start, end});
    }

    // 시작 시간 기준으로 정렬, 시작 시간이 같으면 끝시간이 같은 순서대로 정렬.
    sort(flower.begin(), flower.end());
    
    int endtime = 301;
    if (flower[0].first > endtime){ // 3월 2일 이후로 시작하면 무조건 안됨
        cout << "0\n";
        return 0;
    }
    int i=0;
    int cnt = 0;
    while(endtime <= 1130){ // total endtime이 1130 이상 혹은 모든 애들 다 탐색하면 i를 증가시킨다 
        int new_endtime = 0;
        for(; i<N; i++){
            if (flower[i].first >= flower[i].second) continue; // 당일날 펴서 당일 날 지는 꽃이 있으면 걔는 그냥 제껴야 한다.
            if (endtime >= flower[i].first){  
                if(new_endtime < flower[i].second) // 그 중에서 end time은 max인 걸로 취한다
                    new_endtime = flower[i].second;
            }
            else break;
        }
        if (new_endtime == 0){ // new_endtime 업데이트가 안됨 --> 모든 경우를 다 돌았거나,
            break;
        }
        else {
            endtime = new_endtime;
            cnt++;
        }
    }
    if (endtime > 1130) cout << cnt << '\n';
    else cout << "0\n";
    return 0;
}

 

< 참고한 블로그 >

날짜를 int형 숫자로 나타내는 방식을 못하겠어서 ㅠㅠ 이 아이디어는 이 블로그의 아이디어를 가져왔다.

http://wookje.dance/2017/08/20/boj-2457-%EA%B3%B5%EC%A3%BC%EB%8B%98%EC%9D%98-%EC%A0%95%EC%9B%90/

[BOJ] 2457 : 공주님의 정원