[백준] 공주님의 정원

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

2457번: 공주님의 정원

우선 문제부터 간단하게 요약하면, 

 

꽃들의 피고 지는 시간이 주어졌을 때, 문제에서 준 정원에 특정 시기동안 꽃이 최소 하나이상 피어있도록 하는 최소 꽃의 갯수를 구해야 하는 문제입니다. 

 

<Solution>

피는 날짜를 기준으로 꽃들을 정렬해 놓고, 

 

처음엔 피는 날짜가 3월 1일 보다 작거나 같은 꽃들에 대해 지는 날짜가 가장 긴 꽃을 골라주고, 이후엔 이전에 골랐던 꽃이 지는날 다음날에 대해 3월 1일에 대해 한 것처럼 반복하면 됩니다. 

 

binary search는 bound를 찾을 때도 사용이 가능하다는 점을 통해 사용하여 꽃을 찾았습니다.

 

실제 구현은 아래와 같습니다.

#include <iostream>
#include <algorithm>

using namespace std;

int N;
int sm[100000+10];
int sd[100000+10];
int em[100000+10];
int ed[100000+10];

struct flower{
    int s, e;
}flowers[100000+10];

int month_day[13] = {0, 31, 28, 31, 30, 31, 30, 31, 31, 30, 31, 30, 31};

void InputData(){
    cin >> N;
    for (int i=0; i<N; i++){
        cin >> sm[i] >> sd[i] >> em[i] >> ed[i];
    }
}

int date_to_num(int month, int day){

    int ret = 0;
    for(int i = 1; i<month; i++){
        ret+= month_day[i];
    }
    ret+= day;

    return ret;

}

void build_flowers(){
    for(int i = 0; i<N; i++){
        flowers[i].s = date_to_num(sm[i], sd[i]);
        flowers[i].e = date_to_num(em[i], ed[i])-1;
    }

}

bool compare(struct flower a, struct flower b){
    return a.s < b.s;
}

int solution(){
    build_flowers();

    // 3월 1일 , 11월 30일
    int t1 = date_to_num(3, 1);
    int t2 = date_to_num(11, 30);
    
    // sort by start date

    sort(flowers, flowers+N, compare);

    int num_flower = 0;
    int cur_end = 0;
    
    int s_ = 0;
    while(cur_end <= t2){
        // lowbound 찾기
        int s = s_;
        int e = N-1;
        int sol = -1;
        while(e>=s){
            int mid = (s+e)/2;

            if(flowers[mid].s<=t1){
                sol = mid;
                s = mid+1;
            }
            else{
                e = mid-1;
            }
        }
        if(sol == -1) return 0;

        int f_index = 0;
        for(int i = 1; i<=sol; i++){
            if(flowers[i].e > flowers[f_index].e){
                f_index = i;
            }
        }
        s_ = sol+1;
        t1 = flowers[f_index].e + 1;
        cur_end = t1;
        num_flower++;
    }



    return num_flower;


}


int main(){
    int ans = 0;

    InputData();

    ans = solution();

    cout << ans << endl;
    return 0;
}