문제
3월 1일부터 11월 30일까지 항상 꽃이 피어있도록 하는 최소 꽃의 수를 구하라. 각 꽃의 개화/낙화 기간이 주어진다.
입력
첫째 줄에 N, 이후 N줄에 피는 날과 지는 날(월 일)이 주어진다.
출력
최소 꽃의 수를 출력한다. 불가능하면 0을 출력한다.
예제
| 입력 | 출력 |
|---|---|
4 1 1 5 31 1 1 6 30 5 15 8 31 6 10 12 10 | 2 |
풀이
각 시작일에 대해 가장 늦게 끝나는 꽃을 선택하며 그리디하게 커버한다.
- 날짜를 일수로 변환하여 각 시작일의 최대 종료일을 기록한다
- 3월 1일(60일)부터 시작하여 현재 커버 범위 내 시작하는 꽃 중 가장 멀리 끝나는 꽃을 선택한다
- 11월 30일(335일) 이후까지 커버되면 종료한다
핵심 아이디어: 현재 구간에서 출발 가능한 꽃 중 종료일이 가장 먼 것을 고르는 구간 커버 그리디이다.
코드
package day649;
import java.io.*;
import java.util.*;
public class Day638BOJ2457공주님의정원 {
static final int[] days = { 0, 31, 28, 31, 30, 31, 30, 31, 31, 30, 31, 30, 31 };
public static void main(String[] args) throws Exception {
BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
int N = Integer.parseInt(br.readLine());
int[] endDays = new int[366];
for (int i = 0; i < N; i++) {
int[] arr = Arrays.stream(br.readLine().split(" "))
.mapToInt(Integer::parseInt)
.toArray();
int start = getDay(arr[0], arr[1]);
int end = getDay(arr[2], arr[3]);
endDays[start] = Math.max(end, endDays[start]);
}
int lastDay = 1;
int day = 60;
int ct = 0;
while (day < 335) {
int maxDay = 0;
for (int i = lastDay; i <= day; i++) {
maxDay = Math.max(endDays[i], maxDay);
}
if (maxDay == 0) {
break;
}
lastDay = day;
day = maxDay;
ct++;
}
if (day >= 335) {
System.out.println(ct);
} else {
System.out.println(0);
}
}
static int getDay(int month, int day) {
int ret = 0;
for (int i = 1; i < month; i++) {
ret += days[i];
}
return ret + day;
}
}복잡도
- 시간: O(N + D) - D는 날짜 범위(365), N은 꽃 수
- 공간: O(D)