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

🔔 문제

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

🎯 풀이방법

✔ idea

그리디 문제 중에서 쉬운 축에 속하는 것 같다. 필요한 변수는 꽃을 저장하는 List와 선택한 꽃들의 갯수 count이다.

꽃은 Flower 클래스로 날짜는 Date 클래스를 선언하였다. 각각 날짜 비교와 정렬을 위해 Comparable 인터페이스를 받아 compareTo를 구현하였다. 주의할점은 Date에서는 날짜 오름차순으로 Flower에서는 꽃 지는날 기준 내림차순으로 정렬하도록 하였다.

그리디 알고리즘은 문제 해결 과정에서 그 순간마다 최적의 결정을 수행한다. 공주님의 정원에서는 현재 날짜를 기준으로 최적의 꽃을 선택해야 한다. 이때 최적의 꽃을 선택하는 기준은 2가지이다.

1. 현재 날짜가 꽃의 피는날 ~ 꽃의 지는날 범위에 속하는가? (피는날 ≤ 현재 날짜 ≤ 지는날)
2. 꽃의 지는날이 가장 뒤에 있어야 한다.

출력이 0이 되는 경우는 2가지가 있다.

1. List에 꽃이 없을 때
2. 최적의 조건에 만족하는 꽃이 없을 때
   
   

✔ 알고리즘

1. 현재의 날짜를 기준으로 최적의 꽃을 선택한다
2. count를 1 증가하고 현재날짜를 선택한 꽃의 지는날로 갱신한다
3. 날짜를 체크한다. 만약 현재날짜가 11월 30일보다 크다면 반복을 빠져나간다
   
   

💡 주의할 점

(본문에서..) 예를 들어, 5월 8일 피어서 6월 13일 지는 꽃은 5월 8일부터 6월 12일까지는 꽃이 피어 있고, 6월 13일을 포함하여 이후로는 꽃을 볼 수 없다는 의미이다.

이 글의 의미를 잘 파악해야 한다. 결과적으로 끝나는 날이 11월 30일보다 무조건 커야 한다. 같으면 1번 조건(매일 꽃이 한가지 이상 피어있어야 한다)에 부합하지 않는다.

100%에서 틀렸었는데, count를 출력 전 cur.compareTo(end)<0에서 cur.compareTo(end)<=0로 바꾸어 줬더니 바로 성공하였다. 아마 갱신된 날짜가 11월 30일이라서 그런 것 같다... 추측이므로 정확하지는 않다.

💻 Java code

메모리 57968KB, 시간 628ms

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

public class Main {
    static class Date implements Comparable<Date> {
        int month, day;
        public Date(int month, int day) {
            this.month = month;
            this.day = day;
        }

        @Override
        public int compareTo(Date o) {  // 오름 차순
            if(this.month == o.month) { // 달이 같다면 날짜 비교
                return this.day - o.day;
            }
            return this.month - o.month;
        }

        public void update(int month, int day) {
            this.month = month;
            this.day = day;
        }
    }

    static class Flower implements Comparable<Flower> {
        Date start, end; // 피는날, 지는날

        public Flower(int startM, int startD, int endM, int endD) {
            start = new Date(startM, startD);
            end = new Date(endM, endD);
        }

        @Override
        public int compareTo(Flower o) {  // 꽃 지는날 기준으로 내림차순
            return o.end.compareTo(this.end);
        }
    }

    static int N, count=0;
    static List<Flower> flowerList = new ArrayList<>();

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

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

            int m1,d1,m2,d2;
            m1 = Integer.parseInt(st.nextToken());
            d1 = Integer.parseInt(st.nextToken());
            m2 = Integer.parseInt(st.nextToken());
            d2 = Integer.parseInt(st.nextToken());

            flowerList.add(new Flower(m1,d1,m2,d2));
        }

        Date end, cur;
        end = new Date(11, 30);
        cur = new Date(3, 1);

        // 1-1. 날짜 순으로 내림차순 정렬
        Collections.sort(flowerList);

        while(!flowerList.isEmpty()) {
            // 1. 현재 날짜 기준으로 최적의 결정 pick
            // 1-2. List에서 기한 내에 거르기
            int i;
            for(i=0; i<flowerList.size(); i++) {
                Flower f = flowerList.get(i);

                // 현재날짜 >= 꽃의 피는날
                if(cur.compareTo(f.start)>=0 && cur.compareTo(f.end)<=0) {
                    break;
                }
            }

            // 원하는 꽃이 없을때
            if(i>=flowerList.size()) {
                count = 0;
                break;
            }

            Flower obj = flowerList.remove(i);
            // System.out.println("사용한 꽃 - "+obj);

            // 2. 꽃 고르기
            count++;
            cur.update(obj.end.month, obj.end.day);
            // System.out.println("현재날짜 : "+cur);

            // 3. 날짜 check
            if(cur.compareTo(end)>0) // 현재 날짜 > 11/30
                break;
        }

        // 원하는 꽃이 없을 때
        if(cur.compareTo(end)<=0)  // 현재날짜 < 마지막날
            count = 0;
        System.out.println(count);
    }