<코드업> 4713 : 공주님의 정원

<회고>

필요한 함수들은 금방 떠올랐지만 날짜를 정확하게 맞추는데 꽤나 고생한 문제이다.

처음 문제를 읽으면서 들었던 생각은 각 월의 마지막날 다음날을 어떻게 다음 월의 첫째 날로 생각할 수 있는지에 대한 것이었다.

 

예를 들어, 1월 31일의 다음날이 2월 1일이고, 2월 28일의 다음날은 3월 1일이라는 것을 어떻게 표현할지에 대한 것이었다. 단순히 31을 기준으로 잡기엔 월마다 마지막 날이 다른것이 문제였다.

 

해결책으로 매월, 일, 시는 사실 연속적으로 이어지는 단위를 우리가 이해하기 위한 단위로 끊어놓은 것이므로, 월 / 일을 연속된 단위로 바꾸기 위해 flatten 함수를 만들어 해달 월 / 일을 1년의 몇번째 날인지를 반환하도록 하였다. 날짜를 계산하는 과정에서 하루씩 count 하면 무의미한 연산이 많아지므로, 이전 달 까지의 마지막 날로 빠르게 연산한 후에 해당 달에서만 연산하도록 했다.

 

다음으로, 꽃의 개수가 가장 적게 해야한다는 문제에 대해서는 오래피는 꽃들을 연속적으로 고르면 되는 부분이기 때문에 어렵지 않았다.일단, flag 두개를 사용하여 구간을 설정하도록 하도록 했다. flag가 의미하는 구간은 꽃이 피어있어야만 하는 구간이고, 그 구간 내에서 피기 시작하는 꽃들 중 가장 오래 사는 꽃(Greedy Algorithm) 을 고르면 된다.

 

<세부사항>

 

시작하면서 말했 듯이 문제는 세부적으로 생각하는 부분이 까다로웠다.

 

첫번째로, 피는 구간에 대한 설정이다. 지는 날은 피어있는 날이 아니므로 계산하지 않도록 했고, 살아있는 구간의 계산은 부등호의 구간을 계산하는 방식으로 계산했다.

 

두번째로, 연속적으로 피는 꽃이 없는 경우이다. 중간에 연속적으로 피는 꽃이 없는 경우엔 flag[END] 가 11월 30을 넘기 못하므로 무한 루프가 반복된다. 따라서 연산이 N회(꽃의 종류의 수)가 넘게된다. 즉, 연산의 횟수가 N 회가 넘은 경우엔연속적으로 핀 꽃이 없는 경우 이므로, 해당 경우를 분기로 하여 for문을 벗어 나도록 했다.

 

마지막으로, 꽃이 피어있는 구간이 3월 1일부터 11월 30일 보다 길어야 하고, 꽃이 피어있는 기간이 더 짧으면 안된다.

따라서 flag[END]는 반드시 12월 1일 이후여야 하고, 그 이전이라면 cnt값을 0을 반환하도록 했다. flag[END]는 꽃이 피어있는 마지막 날보다 하루 더 계산한(지는 날 기준)날이다.(이 부분에서 꽤나 시간이 걸렸다.)

 

<Code>

#include <iostream>
using namespace std;

int flatten(int, int);							//월, 일 -> N 번째 날
int flowerCnt(int[][3], int N);
enum Day{START, END, LIVE};
int daysIn[13] = { 0, 31, 28, 31, 30, 31, 30, 31, 31, 30, 31, 30, 31 };
int main() {
	int N;	cin >> N;
	int flower[100000][3] = { 0 };
	for (int i = 0; i < N; i++) {
		int sm, sd, em, ed;
		cin >> sm >>sd >> em >> ed;
		flower[i][START] = flatten(sm, sd);
		flower[i][END] = flatten(em, ed) - 1;
		flower[i][LIVE] = flatten(em, ed) - flatten(sm, sd);
	}
	printf("%d", flowerCnt(flower, N));
}
int flatten(int m, int d) {
	int day = 0;
	for (int i = 1; i < m; i++) day += daysIn[i];
	return day + d;
}
int flowerCnt(int flower[][3], int N) {
	int flag[2] = { 1, flatten(3,1) }; // 3월 1일 기준

	int cnt = 0;
	for (; flag[END] <= flatten(11, 30); cnt++) {
		int max, i;
		i = max = 0;
		for (; i < N; i++) {
			if (flag[START] <= flower[i][START] && flower[i][START] <= flag[END]) {
				if (flower[i][LIVE] - (flag[END] - flower[i][START]) > max)
					max = flower[i][LIVE] - (flag[END] - flower[i][START]);
			}
		}
		flag[START] = flag[END] + 1;
		flag[END] += max;

		if (cnt > N) { cnt = 0; break; }
	}
	if (flag[END] <= flatten(11, 30)) cnt = 0;
	return cnt;
}