백준 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을 출력한다.

예제 입력 1

4
1 1 5 31
1 1 6 30
5 15 8 31
6 10 12 10

예제 출력 1

2

예제 입력 2

10
2 15 3 23
4 12 6 5
5 2 5 31
9 14 12 24
6 15 9 3
6 3 6 15
2 28 4 25
6 15 9 27
10 5 12 31
7 14 9 1

예제 출력 2

5

 

#include <iostream>
#include <vector>
#include <utility>
#include <algorithm>
using namespace std;

int main() {
	int N;
	cin >> N;
	vector<int> Mdate = { 0,31,28,31,30,31,30,31,31,30,31,30,31 };
	
	vector<pair<int, int>> flowering(N, { 0,0 });
	int M, D;

	for (int i = 0; i < N; i++) {
		cin >> M >> D;				//월 일 입력 받기
		for (int j = 0; j < M; j++)
			flowering[i].second += Mdate[j];		//개화시기 일단위로 저장
		flowering[i].second += D;
		cin >> M >> D;				//꽃 지는 시기 일단위로 저장
		for (int j = 0; j < M; j++)
			flowering[i].first += Mdate[j];
		flowering[i].first += D;
	}

	int startMax = Mdate[1] + Mdate[2] + 1;		//3월 1일
	int endMin = 0;
	for (int i = 1; i <= 11; i++) {
		endMin += Mdate[i];
	}	//11월 30일

	sort(flowering.begin(), flowering.end());
	int answer = 0;
	int checkIndex = 0;			//for문 여까지 돌리라
	bool complete = false;		//마지막 요소 잘 찾았으면 true

	for (int i = N - 1; i >= checkIndex; i--) {		//지는 시기가 늦은걸 골라야하니까 밑에서부터 확인하기
		if (flowering[i].second <= startMax) {		//지는 시가가 늦으면서 피는 시기도 오케이면
			if (flowering[i].first == flowering[i].second)	continue;
			answer++;				//꽃 추가
			if (flowering[i].first > endMin) {		//마지막 꽃이면
				complete = true;			//탈출
				break;
			}
			startMax = flowering[i].first;		//이 꽃이 지는 시기를 다음 꽃 개화시기의 커트라인으로
			checkIndex = i+1;					//확인할 인덱스 갱신
			i = N;		//다시 밑에서부터
		}
	}

	if (complete) {
		cout << answer;
	}
	else {
		cout << 0;
	}
}

풀이

그리디 알고리즘을 공부하며 푼 문제라서 규칙을 열심히 찾으려고 노력해봤다. 골드 3문제이지만 조건을 생각하는데는 막 오래걸리진 않았다. 근데 문제 조건을 명확하게 확인을 안했다가 다 풀었는데도 오답이 계속 떠서 잘못된 부분을 찾는데 오래걸렸다.

 

조건 1. 이전에 핀 꽃이 지는 날보다 빨리 꽃이 피어야함(첫번째 꽃을 선택할 때는 이전에 핀 꽃이 지는 날이 아니라 3월 1일 이전에 핀 꽃)

조건 2. 조건1을 만족하는 꽃들 중 가장 늦게 지는 꽃이 선택되어야함.

1. 우선 월과 일이 주어지면 전부 다 일로 변환해서 pair형 벡터에 넣어줌. 이때 조건 2를 위해 지는 날 기준으로 정렬해야하므로 first에 지는 날을 받음.
2. 지는 날을 기준으로 벡터를 정렬해줌
3. 가장 늦은 날짜가 있는 N-1번째 요소부터 for문을 돌려서 조건 1이 맞으면 다음 꽃의 최대 개화일(startMax)을 갱신해주고 answer값을 더해주고 해당 인덱스 위로는 더이상 볼 필요가 없으므로 checkIndex값을 i+1로 갱신헤줌.
4. 마지막으로 개화시킬 꽃이 11월 30일 이후면 값을 잘 구했다고 표시(complete = true)
5. complete값을 보고 answer 또는 0출력

주의할 점. 날짜의 범위를 잘 맞춰줘야함. 지는 날이 11월 30일이면 꽃은 11월 29일까지 존재함. 처음에 이것때문에 오답이 떠서 부등호만 수정해주니 정답이 뜸.