[BOJ] 2457: 공주님의 정원 (JAVA)

문제

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

 

여담

정렬 방식과 대략적인 풀이 흐름은 알겠는데 어떻게 구현해야 할지 모르겠어서 결국 풀이를 참고했다. 여러 번 풀이를 보고 나서야 이해할 수 있었다. 역시 그리디는 너무 어렵다... 다시 또 풀어봐야지

 

그리고 월/일이 주어지는 경우, MMDD 형식과 같이 4자리 숫자 그대로 바로 저장하는 것이 더욱 편리하다는 것을 알게 되었다.

 

24.06.11
다시 풀어봤는데도 어렵다.. 정렬의 순서까지는 생각해 냈는데, 가장 오랫동안 꽃이 피어있어야 하는 것을 어떻게 구현할지 몰라서 결국 또 풀이를 참고했다..ㅎ 나중에 다시 또 풀어봐야겠다😢

 

풀이

이 문제는 그리디 알고리즘으로 풀면 된다. 우선 입력이 MMDD 형식으로 주어지고 날짜를 비교해야 할 일이 많기 때문에, 편의상 MMDD를 4자리 숫자로 그대로 활용한다. 

• 3월 1일 → 301
  • 3 * 100 + 1 = 301
• 11월 30일 → 1130
  • 11 * 100 + 30 = 1130

 

꽃의 개화 시기를 입력받은 뒤, 개화 시작일을 기준으로 오름차순 정렬을 수행한다. 만약 시작일이 같다면 개화 종료일을 기준으로 내림차순 정렬을 수행하면 된다. 그 이유는 다음과 같다.

• 1월에서 12월까지 순차적으로 진행되므로, 가장 앞에서부터 계산해 나가야 한다.
  • 따라서 시작일을 기준으로 오름차순 정렬하기
• 시작일이 같다면, 종료일이 늦을수록 더 적은 꽃을 사용할 수 있다.
  • 따라서 종료일을 기준으로 내림차순 정렬하기

 

또한 꽃이 11월 30일까지 피어있어야 하므로, 종료일이 12월 1일 이상인 꽃을 마지막으로 선택하면 된다. 왜냐하면 종료일이 12월 1일이어야 꽃이 11월 30일까지 피어있기 때문이다. (∵ 문제에 주어진 조건)

 

 

이렇게 정렬이 끝나면 다음과 같은 내용을 고려하여 선택한 꽃의 최소 개수를 구하면 된다. 자세한 내용은 아래의 코드를 참고하면 된다.

• 매일 꽃이 한 가지 이상 피어있기 위해서 이전에 선택한 꽃의 종료일보다 늦게 개화하는 꽃을 선택하면 안된다. 
• 최소한의 꽃을 선택하기 위해서는 가장 오래 피어있는 꽃을 찾아야 한다.
• 12월 이후에 피는 꽃을 찾는 것은 의미가 없기 때문에, 12월 1일까지만 찾으면 된다. 

 

코드

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

public class Main {
    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        int N = Integer.parseInt(br.readLine());
        Flower[] flowers = new Flower[N];
        for (int i = 0; i < N; i++) {
            StringTokenizer st = new StringTokenizer(br.readLine(), " ");
            int startMonth = Integer.parseInt(st.nextToken());
            int startDay = Integer.parseInt(st.nextToken());
            int endMonth = Integer.parseInt(st.nextToken());
            int endDay = Integer.parseInt(st.nextToken());

            int start = startMonth * 100 + startDay;
            int end = endMonth * 100 + endDay;
            flowers[i] = new Flower(start, end);
        }

        Arrays.sort(flowers, (f1, f2) -> {
            if (f1.start == f2.start) return f2.end - f1.end; // 시작일이 같다면 종료일을 기준으로 내림차순 정렬
            return f1.start - f2.start; // 시작일을 기준으로 오름차순 정렬
        });

        int startDay = 301, endDay = 1201;
        int idx = 0, max = 0, answer = 0;
        while (startDay < endDay) {
            boolean isFind = false; // 꽃을 찾았는지 확인하기 위해
            for (int i = idx; i < N; i++) {
                // 시작일보다 늦게 시작하면 의미없음
                if (flowers[i].start > startDay) break;

                // 가장 오래 피어있는 꽃 찾기
                if (flowers[i].end > max) {
                    max = flowers[i].end; // 가장 늦게 끝나는 종료일 찾기
                    isFind = true;
                    idx = i + 1; // 다음 탐색 시, 현재 인덱스의 다음부터 탐색하도록 (=가지치기) 
                }
            }

            if (isFind) { // 사용할 꽃을 찾은 경우
                answer++; 
                startDay = max; // 시작일 갱신하기
            } else break;
        }
        if (max < endDay) System.out.println(0);
        else System.out.println(answer);
    }

    static class Flower {
        int start, end;

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

---

참고

https://maivve.tistory.com/324