[C/C++] 코드업(codeup) 4713번 공주님의 정원

▽문제 바로가기

https://codeup.kr/problem.php?id=4713

공주님의 정원

---

입력

첫째 줄에는 꽃들의 총 개수 N (1<=N<=100,000)이 주어진다.

다음 N개의 줄에는 각 꽃이 피는 날짜와 지는 날짜가 주어진다. 하나의 날짜는 월과 일을 나타내는 두 숫자로 표현된다.

예를 들어서, 3 8 7 31은 꽃이 3월 8일에 피어서 7월 31일에 진다는 것을 나타낸다.

 

출력

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

 

문제 풀이

 

그리디 문제입니다.

 

역시 현재 날짜를 기준으로 가장 오랫동안 피어있는 꽃을 선택하면 됩니다.

11월 30일까지 꽃이 피어있어야하니 최소 12월 1일에 꽃이 질 때까지 선택해야 합니다.(11월은 30일까지)

 

이 문제에 적용해볼만한 사항입니다.

1. 월, 일 처리를 월에 100을 곱하여 편하게 처리하기.

월에 100을 곱하여 편리하게 할 수 있습니다. 3월 1일을 301, 11월 30일을 1130과 같이 표현할 수 있죠.

 

2. 꽃들을 정렬하여 속도 올리기.

꽃들은 최대 100000(십만)개의 입력을 가집니다. 365 일이라고 해도 완전 탐색 시 3천만이기에 1초 이내로 계산은 가능합니다. 하지만, 정렬을 하면 속도가 빠르겠죠.

 

#include <stdio.h>

using namespace std;

int n;
int arr[100001][4];
int month = 3, day = 1; 	//현재 월, 일

void greedy(){
	
	//[0] : 월, [1] : 일
	int max[2] = {0,};	//현재기준으로 가장 오래피는 꽃 선택 
	for(int i=0;i<n;i++){
		int temp[2] = {0,};	//지금 선택한 꽃의 남은 월, 일 확인 
		//현재기준으로 꽃이 지지않았다면 
		if((arr[i][2]>month)||(month==arr[i][2]&&arr[i][3]>=day)){
			//꽃이 피었다면
			if((arr[i][0]<month)||(month==arr[i][0]&&arr[i][1]<=day)){
				temp[0] = arr[i][2];
				temp[1] = arr[i][3];
			}
		}
		//더 오래피는 꽃이라면
		if((max[0]<temp[0])||(max[0]==temp[0]&&max[1]<temp[1])){
			max[0] = temp[0];
			max[1] = temp[1];
		}
	}
	
	month = max[0];
	day = max[1];

}

int main(){
	
	scanf("%d", &n);
	
	for(int i=0;i<n;i++){
		for(int j=0;j<4;j++){
			scanf("%d", &arr[i][j]);
		}
	}
	
	int cnt = 0;
	for(;;){
		if(month>=12) break;
		cnt++;
		int temp_month = month, temp_day = day;
		greedy();
		//조건을 만족하는 꽃들을 선택할 수 없다면
		if(temp_month==month&&temp_day==day){
			cnt = 0;
			break;
		}
	}
	
	printf("%d", cnt);
	
}