[BOJ/Greedy] 백준 2457 - 공주님의 정원 (Java)

2457 - 공주님의 정원

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

문제

총 N개의 꽃, 모두 같은 해에 피어서 같은 해에 짐
하나의 꽃은 피는 날과 지는 날이 정해져 있음
ex. 5/8에 피어서 6/13일 지는 꽃은: 5/8 ~ 6/12 꽃이 피어 잇고, 6/13 포함한 이후는 꽃을 볼 수 없음
(올해: 4, 6, 9, 11월 - 30일, 1, 3, 5, 7, 8, 10, 12월 - 31일, 2월 - 28일)

이러한 N개의 꽃들 중에서 두 조건을 만족하는 꽃 선택
1. 가장 좋아하는 계절인 3/1 ~ 11/30 매일 꽃이 한 가지 이상 피어 있도록 함
2. 정원이 넓지 않으므로 꽃들의 수를 가능한 적게 함

입력
첫째 줄: 꽃들의 총 개수 N (1 <= N <= 100,000)
다음 N개의 줄: 각 꽃이 피는 날짜, 지는 날짜
ex. 3 8 7 31: 3/8에 펴서 7/31에 짐
출력: 선택한 꽃들의 최소 개수, 두 조건을 만족하는 꽃들 선택 X -> 0

---

풀이

• `start`, `end` -> MMDD 형식으로 변환
  • ex. 3 8(: 3/8) -> 308
• 최대한 오래 피어 있는 꽃 먼저 선택
  • 시작일 오름차순 정렬
  • 시작일 같으면 끝나는 날짜 더 늦은 것부터(내림차순) 정렬

class Flower implements Comparable<Flower> {
    int start, end;

    public Flower(int sm, int sd, int em, int ed) {
        this.start = sm * 100 + sd;
        this.end = em * 100 + ed;
    }

    @Override
    public int compareTo(Flower o) {
        if (this.start != o.start) return this.start - o.start;
        else return o.end - this.end;
    }
}

---

예시

// 입력
4
1 1 5 31 -> 101 ~ 531
1 1 6 30 -> 101 ~ 630
5 15 8 31 -> 515 ~ 831
6 10 12 10 -> 610 ~ 1210

• 현재: 301(: 3/1) 
  • 꽃1: 101531 vs 꽃2: 101630
    • 꽃2 선택 -> end: 630 
• 현재: 630(: 6/30)
  • 꽃3: 515831 vs 꽃4: 6101210
    • 꽃4 선택 -> end: 1210

=> 2개(3/1 ~ 11/30까지 매일 꽃 한 가지 이상 O)

start <= 꽃 시작일 , 기간 더 길어야 함

---

 

코드

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

// 공주님의 정원
class Flower implements Comparable<Flower> {
    int start, end;

    public Flower(int sm, int sd, int em, int ed) {
        this.start = sm * 100 + sd;
        this.end = em * 100 + ed;
    }

    @Override
    public int compareTo(Flower o) {
        if (this.start != o.start) return this.start - o.start;
        else return o.end - this.end;
    }
}

public class boj_2457 {
    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 sm = Integer.parseInt(st.nextToken());
            int sd = Integer.parseInt(st.nextToken());
            int em = Integer.parseInt(st.nextToken());
            int ed = Integer.parseInt(st.nextToken());
            flowers[i] = new Flower(sm, sd, em, ed);
        }

        Arrays.sort(flowers);

        int cnt = 0;
        int currEnd = 301;
        int idx = 0;

        while (currEnd <= 1130) {
            int maxEnd = currEnd;
            while (idx < N && flowers[idx].start <= currEnd) {
                if (flowers[idx].end > maxEnd) {
                    maxEnd = flowers[idx].end;
                }
                idx++;
            }
            if (maxEnd == currEnd) {
                System.out.println(0);
                return;
            }
            cnt++;
            currEnd = maxEnd;
        }

        System.out.println(cnt);
    }
}