BOJ 2457 공주님의 정원 [Java]

BOJ 2457 공주님의 정원

1. 문제 링크

https://www.acmicpc.net/problem/2457

2. 문제 해설

그리디 알고리즘을 이용하여 푸는 문제이다. 백준 문제 중 1931번 회의실 배정과 비슷한 결을 가진 문제이다. 1931번을 풀어보지 않았다면 먼저 풀어보도록 하자.
https://www.acmicpc.net/problem/1931

다시 문제로 돌아와서, 일단 그리디를 이용해서 풀면 될 것 같다는 생각은 들었지만 그리디를 이용하려면 검증이 필요하다. 매번 최선의 선택을 한 것이 전체적으로 봤을 때도 최선의 답이라는 것을 검증해야한다. 그 전에 일단 내가 어떻게 문제를 그리디적으로 접근했는지 살펴보자.

1. 3월 1일을 기준일로 잡는다.
2. 기준일보다 일찍 피는 꽃들 중에서 가장 지는 날짜가 늦은 꽃을 선택한다.
3. 선택한 꽃의 지는 날짜를 기준일로 잡는다.
4. 기준일이 11월 30일을 초과할 때까지 2,3번을 반복한다.

매번 기준일보다 일찍 피는 꽃들 중에서 가장 늦게 지는 꽃을 선택하는 것이 최적해가 된다는 것을 검증하기 위해 귀류법적으로 생각해보자.
가장 늦게 지는 꽃말고 더 일찍 지는 꽃을 선택하는 것이 최적해에 포함된다고 기정해보자. 가장 늦게 지는 꽃을 선택할 때보다 더 많은 꽃을 선택하게 되는 경우가 생긴다. 즉, 가정에 모순이 생기고 가장 늦게 지는 꽃을 선택하는 것이 최적해라고 생각할 수 있다.

문제의 답을 얻기 위한 과정을 구현하는 과정에서 신경써줘야 하는 부분을 살펴보자.
- 꽃들의 피는 날짜와 지는 날짜를 담기 위해 Term 클래스를 만들어주었다.
- 날짜를 처리할 때, 대소비교를 쉽게 하기 위하여 월에다가 100을 곱하고 일을 더하여 저장하는 방식을 이용했다. 예를 들어 3월 1일이라면 3 x 100 + 1로 301로 저장하였다.
- 문제에서 주어진 조건이 2가지인데 첫째는 정원이 넓지 않으므로 정원에 심는 꽃들의 수를 가능한 적게 한다이고 둘째는 공주가 가장 좋아하는 계절인 3월 1일부터 11월 30일까지 매일 꽃이 한 가지 이상 피어 있도록 한다이다. 두번째 조건을 만족하지 못하는 경우가 생길 수 있다. 3가지로 나누어 볼 수 있다. 모든 꽃의 피는 시기가 3월 1일 이후인 경우, 중간에 비는 시기가 생기는 경우, 모든 꽃의 지는 시기가 11월 30일 이전인 경우이다. 초기 3월 1일로 잡았던 기준일이 새롭게 갱신되지 않는다면 3가지 경우 중 한가지인 것이라는 점을 이용하여 check 변수를 써서 해결하였다.

3. 코드 보기

import java.io.*;
import java.util.StringTokenizer;

public class Main {
    static class Term {
        int start;
        int end;

        public Term(int start, int end) {
            this.start = start;
            this.end = end;
        }
    }

    static int n;
    static Term[] flower;
    static int flag = 301;
    static int ans = 0;

    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));

        n = Integer.parseInt(br.readLine());
        flower = new Term[n];

        for (int i = 0; i < n; i++) {
            StringTokenizer st = new StringTokenizer(br.readLine());
            int sMonth = Integer.parseInt(st.nextToken());
            int sDay = Integer.parseInt(st.nextToken());
            int eMonth = Integer.parseInt(st.nextToken());
            int eDay = Integer.parseInt(st.nextToken());

            flower[i] = new Term(sMonth * 100 + sDay, eMonth * 100 + eDay);
        }

        while (flag < 1201) {
            int maxEnd = flag;
            boolean check = false;

            for (int i = 0; i < n; i++) {
                if (flower[i].start <= flag) {
                    if (flower[i].end > maxEnd) {
                        maxEnd = flower[i].end;
                        check = true;
                    }
                }
            }

            if (check) {
                flag = maxEnd;
                ans++;
            } else {
                ans = 0;
                break;
            }
        }

        bw.write(Integer.toString(ans));
        br.close();
        bw.flush();
        bw.close();
    }
}