[백준 / 골드3] 2457 공주님의 정원 (Java)

문제 보기

사용한 것

• 항상 꽃이 피어있는 최소의 꽃 개수를 구하기 위한 그리디
• 월별로 날짜의 수를 저장한 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;
    }
}