백준 2457번 공주님의 정원 (C++)

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

2457번: 공주님의 정원

 

처음 문제를 보고 투포인터 이분탐색이 생각났다.

처음 꽃은 반드시 3월 1일 이하부터 피어야하고 마지막 꽃은 12월 1일 이하에 져야한다. 그러므로 각 포인터들을 이동시켜서 최적의 조건을 만든 후 checking 절차를 하면 된다고 생각했다.

 

결론적으로 말하면 위 방법이 완전히 틀린 것은 아니지만 이렇게할 필요도 없고 문제의도와 맞지 않다.

이 문제의 의도는 Greedy 이다. 그리디가 어려운 점은 구현과 많이 다르지 않고 사람마다 코드 스타일이 달라 어떻게 구현할지 어렵다.

 

이 문제를 풀며 나의 단점을 다시 한 번 알았다.

 

1. 너무 예외처리를 하려고한다.

2. 너무 러프하게 접근한다. 모든 경우를 아우르는 코드를 짜야한다.

3. 전재조건을 깔고가지 않는다.

 

이 문제는 시작이 3월 1일이고 끝나는 날이 12월 1일과 가장 가까운 것이 해답이다. 그러므로 이 두개의 기준점을 가지고 가며 문제를 풀이하는 것이 좋다. 그리고 꽃을 가장 적게 심어야하기 때문에 최대한 간격이 긴 꽃을 선택해야하며 각 꽃들의 간격이 최대여야할 것이다. 

 

그러므로 정렬 기준은 "가장 빠르게 피면서 가장 늦게 지는 꽃" 이다.

 

먼저 StartDay, EndDay를 가정한다. StartDay는 현재 꽃이 피는날 EndDay는 꽃이 지는 날이다. 301 1201로 지정한다.

 

그 다음 첫번째 꽃을 확인한다. 

만약 첫번째 피는 꽃의 피는날이 2월 23일이라 가정하자. 3월 1일보다 작으므로 이 꽃은 선택가능하다. 그리고 정렬 기준에 따라 가장 늦게 지는 꽃 순서로 배치했으므로 같은 날에 피는 꽃들을 생각하지 않아도 된다.

 

이 꽃을 선택하였다면 이 꽃을 기준으로 몇 개의 꽃들이 스킵가능한지 알아봐야한다. 스킵이 가능하다는 것은, 선택한 지금 꽃이 지는날이 다음 꽃이 지는날보다 늦다는 것을 뜻한다. 

예를들어 지금 꽃이 4월 2일에 진다. 그런데 다음 꽃은 4월 1일에 진다. 그렇다면 다음 꽃을 선택할 이유가 없다. 

 

이제 이것을 코드로 표현해보자!!

 

for (int i = idx; i < N; i++) {				// 다음 꽃 부터 현재 꽃과 비교
	if (flower[i].first > startDay) break;  // 이번에 비교하는 꽃의 시작이 현재 피어있는 꽃이 지는날 보다 늦게 피면 선택 불가
    
	if (NowEndDay < flower[i].second) { 	// 만약 지금 피어있는 꽃이 비교하는 꽃 보다 늦게피면 즉, 넘어가야하면
		idx = i + 1;				// 이 다음 꽃부터 비교해야하므로 인덱스는 i + 1
		NowEndDay = flower[i].second;		// 꽃을 새로 선택하고 끝나는 날을 선정
	}
}

 

여기서 중요한 것은 두번째 if문에서 새로운 꽃을 선택하고 바로 꽃의 개수를 늘리지 않는 것이다. 

지금 5월10일~ 7월 14일에 지는 꽃이라 하자. 

그리고 다음 꽃들은

7월 10일~9월 12일

7월 11일~10월 1일

8월 10일~11월 4일

 

이라하자. 현재 NowEndDay = 7월14일이다.

그렇다면 9월 12일보다 작으므로 인덱스가 갱신되고 NowEndDay = 10월 1일이 된다.

여기서 끝내버리면 원래 7월 11일을 선택해야하는데 7월 10일을 선택하고 꽃이 + 1 되어버린다. 이러면 안된다.

중요한 것은 아직 첫번째 if문의 startDay는 갱신되지 않았다. startDay는 아직 7월 14일이다.

그러므로 다음 7월 11일도 선택가능하다. 그 다음엔 7월 14일보다 8월 10일 이크므로 첫번째 if문에서 break된다. 

그리고 이제 꽃의 개수를 + 1 하고 startDay를 NowEndDay로 지정해준다. 즉, 시작하는날 = 10월 1일이 된다. 이제 다음 꽃인 8월 10일에 들어갈 수 있다.

 

이제 모든 탐색이 끝났다. 그런데, NowEndDay, 즉 마지막 꽃의 끝나는 날이 11월 4일이다. 12월 1일보다 작다! 그러므로 답은 0을 출력한다. 

 

논리적으로 생각하고 그것을 코드로 옮기는 것이 어려운 문제였다. 언제나 손으로 먼저 풀고 코드로 옮기는 연습을 하자. 그리고 간결하게 쓰려 노력하고 예외처리를 심하게 하면 예상치 못한 것 까지 예외처리된다.

 

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

using namespace std;

bool comp(pair<int, int>&a, pair<int, int>&b){
    if(a.first < b.first) return true;
    else if(a.first == b.first){
        return a.second > b.second;
    }else return false;
}

vector<pair<int, int>> vec;

int main(){
    int N;
    cin >> N;
    
    for(int i = 0; i < N; i++){
        int a, b, c, d;
        cin >> a >> b >> c >> d;
        vec.push_back({a*100 + b, c*100 + d});
    }
    
    sort(vec.begin(), vec.end(), comp);
    
    int idx = 0;
    int end_day = 1201;
    int start_day = 301;
    int answer = 0;
    int nextStart = 0;
    while(start_day < end_day){
        bool flag = false;

        for(int i = idx; i < N; i++){
            if(vec[i].first > start_day) break; // 새로운 꽃 선택 할 수 없음. 이 꽃이 지는 날 보다 다음 꽃이 늦게 핌
            
            if(nextStart < vec[i].second){ // 새로운 꽃을 선택하고 꽃이 지는날을 시작일로 선택하기 위해 저장
                idx = i + 1;
                flag = true;
                nextStart = vec[i].second;
            }
        }
        
        if(flag){
            answer++;
            start_day = nextStart; // 다음 시작일 = 지금 꽃이 지는 날
        }else{
            break; // 꽃을 새로 선택하지 못했음.
        }
    }
    //cout << nextStart << " " << end_day << endl;
    if(nextStart < end_day) cout << 0 << '\n';
    else cout << answer << '\n';
    
    return 0;
}