[백준] 2457번 : 공주님의 정원

문제

 

 

접근 방식

우선 문제를 정리해 보면

꽃이 피는 날과 지는 날이 주어졌을 때

피는 날을 포함한 날부터 꽃이 피기 시작하고

지는 날을 포함하지 않은 날까지 꽃이 피어있는다.

 

정원에 꽃이 하나라도 피어 있는 상태를 유지하기 위해선

이전에 핀 꽃이 지기 전이나 지자 마자

바로 다음 꽃이 피어 있어야 하기 때문에

이전에 심은 꽃들 중 가장 늦게 지는 날보다 

전이거나 지는 당일에 꽃이 피는 경우에만 심을 수 있다.

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, 15, 3, 23
2, 28, 4, 25
4, 12, 6, 5
5, 2, 5, 31
6, 3, 6, 15
6, 15, 9, 3
6, 15, 9, 27
7, 14, 9, 1
9, 14, 12, 24
10, 5, 12, 31

 

위의 경우에 최소한의 꽃을 심는 경우는

2.28 ~ 4.25 >> 4.12 ~ 6.5 >> 6.3 ~ 6.15 >> 6.15 ~ 9.27 >> 9.14 ~ 12.24로

5번 꽃을 심어서 정원에 꽃이 핀 상태를 유지할 수 있다.

 

우선 3월 1일 이전에 피고 이후에 지는 꽃 중에서

가장 늦게 지는 꽃을 시작점으로 한 후에

이후 나머지 꽃들의 주기를 살펴보면서

이전 꽃이 지기 전이나 직후에 필 수 있고

이전 꽃보다 늦게 지는 경우에 꽃을 심는다.

 

조심해야 할 부분은 꽃이 필 수 있는 경우라도

더 효율적인 경우 하나만을 골라야 하기 때문에

이전까지 핀 꽃들 중 가장 늦게 지는 꽃보다

오래 피는 꽃만 선택해야 한다.

 

풀이

public class Main {

	public static void main(String[] args) throws IOException {
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		StringTokenizer st;

		int n = Integer.parseInt(br.readLine());

		int[][] flowers = new int[n][4];

		for (int i = 0; i < n; i++) {
			st = new StringTokenizer(br.readLine());

			flowers[i][0] = Integer.parseInt(st.nextToken());
			flowers[i][1] = Integer.parseInt(st.nextToken());
			flowers[i][2] = Integer.parseInt(st.nextToken());
			flowers[i][3] = Integer.parseInt(st.nextToken());
		}

		Arrays.sort(flowers, (o1, o2) -> {
			if (o1[0] != o2[0]) {
				return o1[0] - o2[0];
			} else {
				if (o1[1] != o2[1]) {
					return o1[1] - o2[1];
				} else {
					if (o1[2] != o2[2]) {
						return o1[2] - o2[2];
					} else {
						return o1[3] - o2[3];
					}
				}
			}
		});

		int min = 0;
		int psm = 0;
		int psd = 0;
		int pem = 0;
		int ped = 0;

		for (int i = 0; i < n; i++) {
			int sm = flowers[i][0];
			int sd = flowers[i][1];
			int em = flowers[i][2];
			int ed = flowers[i][3];

			if (sm < 3 || (sm == 3 && sd == 1)) {
				if (em < pem || (em == pem && ed <= ped)) continue;
				min = 1;
				psm = sm;
				psd = sd;
				pem = em;
				ped = ed;
				if (end(pem, min))
					return;
				continue;
			}

			if (min == 0) continue;

			if (sm < psm || sm == psm && sd <= psd) {
				if (em < pem || (em == pem && ed <= ped)) continue;
				pem = em;
				ped = ed;
				if (end(pem, min))
					return;
				continue;
			}

			if (sm < pem || (sm == pem && sd <= ped)) {
				min++;
				psm = pem;
				psd = ped;
				pem = em;
				ped = ed;
			}

			if (end(pem, min))
				return;
		}

		System.out.println(0);
	}

	private static boolean end(int pem, int min) {
		if (pem > 11) {
			System.out.println(min);
			return true;
		}
		return false;
	}
}