사용한 것
- 항상 꽃이 피어있는 최소의 꽃 개수를 구하기 위한 그리디
- 월별로 날짜의 수를 저장한
days
- 몇월 몇일인지 주어지면 365일 중 몇 번째 날에 해당되는지 반환하는
getDay()
풀이 방법
- 366의 크기만큼(1일 ~ 365일 계산하기 쉽게)
endDays
를 만들어 꽃이 피는 날짜를 인덱스로, 꽃이 지는 날짜를 값으로 getDay()
를 사용하여 저장한다.
- 저장할 때 같은 날에 피는 꽃은 더 나중에 지는 것으로 저장한다.
- 3월 1일 부터 꽃이 피어야 되니
day
를 60으로, 11월 30일 까지 꽃이 피어야 되니 day
가 335보다 작을 때까지 while문을 돌린다.
maxDay
에 이미 계산이 끝난 lastDay
부터 항상 꽃이 피기 위하여 day
까지 가장 늦게 지는 꽃의 지는 날짜를 저장한다.
maxDay
가 처음에 선언한 값인 0이면 더 이상 꽃이 필 수 없으므로 break 한다.
- 꽃이 한개 사용되었으므로
ct
를 증가시키고 lastDay
에 이미 계산이 끝난 날짜를 넣어주고 day
를 계산한 가장 늦게 지는 꽃의 지는 날짜를 저장한다.
- 반복문이 끝난 뒤 만약
day
가 335보다 크거나 같으면 11월 30일까지 항상 꽃이 필 수 있으므로 ct
를 반환한다.
코드
public class Main {
static final int[] days = {0, 31, 28, 31, 30, 31, 30, 31, 31, 30, 31, 30, 31};
public static void main(String[] args) throws IOException {
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;
}
}