BOJ(C++) / 백준 2457 : 공주님의 정원

백준 2457 : 공주님의 정원

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

2457번: 공주님의 정원

 

문제

오늘은 공주님이 태어난 경사스러운 날이다. 왕은 이 날을 기념하기 위해 늘 꽃이 피어있는 작은 정원을 만들기로 결정했다.

총 N개의 꽃이 있는 데, 꽃은 모두 같은 해에 피어서 같은 해에 진다. 하나의 꽃은 피는 날과 지는 날이 정해져 있다. 예를 들어, 5월 8일 피어서 6월 13일 지는 꽃은 5월 8일부터 6월 12일까지는 꽃이 피어 있고, 6월 13일을 포함하여 이후로는 꽃을 볼 수 없다는 의미이다. (올해는 4, 6, 9, 11월은 30일까지 있고, 1, 3, 5, 7, 8, 10, 12월은 31일까지 있으며, 2월은 28일까지만 있다.)

이러한 N개의 꽃들 중에서 다음의 두 조건을 만족하는 꽃들을 선택하고 싶다.

1. 공주가 가장 좋아하는 계절인 3월 1일부터 11월 30일까지 매일 꽃이 한 가지 이상 피어 있도록 한다.
2. 정원이 넓지 않으므로 정원에 심는 꽃들의 수를 가능한 적게 한다. 

N개의 꽃들 중에서 위의 두 조건을 만족하는, 즉 3월 1일부터 11월 30일까지 매일 꽃이 한 가지 이상 피어 있도록 꽃들을 선택할 때, 선택한 꽃들의 최소 개수를 출력하는 프로그램을 작성하시오. 

 

입력

첫째 줄에는 꽃들의 총 개수 N (1 ≤ N ≤ 100,000)이 주어진다. 다음 N개의 줄에는 각 꽃이 피는 날짜와 지는 날짜가 주어진다. 하나의 날짜는 월과 일을 나타내는 두 숫자로 표현된다. 예를 들어서, 3 8 7 31은 꽃이 3월 8일에 피어서 7월 31일에 진다는 것을 나타낸다. 

 

출력

첫째 줄에 선택한 꽃들의 최소 개수를 출력한다. 만약 두 조건을 만족하는 꽃들을 선택할 수 없다면 0을 출력한다.

 

코드

//백준 2457 공주님의 정원
#include <iostream>
#include <vector>
#include <algorithm>

using namespace std;

//꽃이 피는 날짜가 앞인 순으로 정렬
bool cmp(vector<pair<int, int>>& a, vector<pair<int, int>>& b) {
	if (a[0].first == b[0].first) {
		return a[0].second < b[0].second;
	}
	return a[0].first < b[0].first;
}

//날짜 비교 더 큰 날짜 return
pair<int, int> day_compare(pair<int, int>& a, pair<int, int>& b) {
	if (a.first < b.first)
		return b;
	else if(a.first == b.first){
		if (a.second < b.second)
			return b;
	}
	return a;
}

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

	//입력
	int N;
	cin >> N;
	vector<vector<pair<int, int>>> day;
	for (int i = 0; i < N; i++) {
		int s_m, s_d, e_m, e_d;
		cin >> s_m >> s_d >> e_m >> e_d;
		vector<pair<int, int>> v;
		v.push_back(make_pair(s_m, s_d));
		v.push_back(make_pair(e_m, e_d));
		day.push_back(v);
	}

	sort(day.begin(), day.end(), cmp); //정렬

	int count = 0;
	pair<int, int> temp_s = { 3,1 }; //3월 1일
	pair<int, int> temp_e = { 12, 1 };
	pair<int, int> temp = { 1,1 };
	int check = 0;

	for (int i = 0; i < N; i++) {
		//기준 위치보다 빠를경우
		if (day_compare(temp_s, day[i][0]) == temp_s) {
			temp = day_compare(temp, day[i][1]);
			//11월 30일 이후
			if (day_compare(temp, temp_e) == temp) {
				check = 1;
				break;
			}
		}
		//기준 위치보다 이후일 때
		else {
			temp_s = temp; //기준 위치 temp로 변경
			count++; //종류 하나 증가
			//기준 위치보다 다음 꽃의 날짜가 앞에 있을 때 
			if (day_compare(temp_s, day[i][0]) == temp_s) {
				temp = day[i][1];
				//12월 1일보다 날짜가 뒤일 때
				if (day_compare(temp, temp_e) == temp) {
					check = 1;
					break;
				}
			}
			//기준 위치보다 다음 꽃의 날짜가 뒤에 있을 때 
			else
				break;
		}
	}

	if (check == 0)
		cout << "0\n";
	else
		cout << count + 1 << "\n";


	return 0;
}

 

설명

• 꽃이 피는 날짜가 앞인 순으로 정렬한다.
• 처음 기준 위치는 3월 1일(temp_s)이다. 
• 기준 위치보다 꽃이 피는 날짜가 이른 날짜 중 지는 날짜가 가장 늦은 날짜를 temp로 지정한다. 이때 temp가 12월 1일 이후라면 check를 1로 변경하고 반복문을 종료한다.
• 기준 위치보다 꽃이 피는 날짜가 늦으면 기준 위치를 temp로 변경하고 count를 증가한다.
• 기준 위치보다 다음 꽃의 날짜가 뒤에 있다면 중간에 꽃의 공백이 생기므로 종료한다. 그렇지 않다 temp를 지는 날짜로 변경해주고 12월 1일 이후라면 check를 1로 변경하고 반복문을 종료한다.

그림으로 설명해보면 temp_s와 temp, temp_e가 다음과 같이 움직인다.

 

고찰

걸린 시간 : 2시간 이상

프로그래머스에서 비슷한 문제를 푼 적이 있어 쉽게 문제를 풀 거라 생각했지만,,, 오산이었다...

생각보다 해결법은 금방 생각했지만, 조건 중에서 '5월 8일 피어서 6월 13일 지는 꽃은 5월 8일부터 6월 12일까지는 꽃이 피어 있고, 6월 13일을 포함하여 이후로는 꽃을 볼 수 없다는 의미이다.'라는 조건을 확인하지 못해서 20%에서 결국 해결하지 못하고 검색하여 문제를 해결할 수 있었다.. 

IDE에서 디버깅하는 것이 익숙해져서 디버깅 없이 문제를 바로 해결할 수 있도록 해야겠다.

 

난이도(solved)

Gold 4