22.03.16 - [BOJ] 2457. 공주님의 정원

[suhyunsim]

문제

• 공주님의 정원

핵심 아이디어

• 피어있는 날: ~지는 날 - 1
• 정원에는 최소한만 심기
• 3/1 ~ 11/30: 최소 하나 꽃이 피어있어야 함
• return 0이 되는 경우
  1) 3/1 이후에만 피는 경우
  2) 중간에 아무 꽃도 안 피는 경우
  3) 모든 꽃이 11/30 이전에 지는 경우
• 월/일은 일이 최대 두자리니까 월을 * 100으로 계산해서 비교해버리기
• 그리디 활용
  1. START: 3/1, 초기 기준
  2. 3/1 이전에 피면서 (3/1도 포함) 가장 늦게 지는 꽃의 지는 날짜 구하기
  3. 지는 날짜를 다시 기준으로
  4. 기준 날짜 이전에 피면서 가장 늦게 지는 꽃의 지는 날짜 구하기 -> 2) ~ 3) 반복
  5. 11/30 초과 될 때 cnt 구하고 종료

어려운 점, 실수

풀이

package main.java.com.poogle.BOJ.Q2457;

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.HashMap;
import java.util.Map;
import java.util.StringTokenizer;

public class Main {
    static final int START = 301;
    static final int END = 1201;

    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        int n = Integer.parseInt(br.readLine());
        Map<Integer, Integer> flowers = new HashMap<>();
        int cnt = 0;
        for (int i = 0; i < n; i++) {
            StringTokenizer st = new StringTokenizer(br.readLine());
            int start = getDates(Integer.parseInt(st.nextToken()), Integer.parseInt(st.nextToken()));
            int end = getDates(Integer.parseInt(st.nextToken()), Integer.parseInt(st.nextToken()));
            if (flowers.get(start) == null || flowers.get(start) < end) {
                flowers.put(start, end);
            }
        }
        boolean flag = false;
        int now = START;
        //11월 30일 전까지
        while (now < END) {
            int max = now;
            for (int key : flowers.keySet()) {
                /*
                지금보다 먼저 피는 꽃 중에서 가장 늦게 지는 꽃
                 */
                if (key <= now && max < flowers.get(key)) {
                    max = flowers.get(key);
                    flag = true;
                }
            }
            if (flag) {
                now = max;
                flag = false;
                cnt++;
            } else {
                /*
                1) 3/1 이후에만 피는 경우
                2) 중간에 아무 꽃도 안 피는 경우
                3) 모든 꽃이 11/30 이전에 지는 경우
                 */
                cnt = 0;
                break;
            }
        }
        System.out.println(cnt);

    }

    private static int getDates(int month, int day) {
        return month * 100 + day;
    }
}