[백준] 2457 공주님의 정원

 

🔒 문제

🧠 아이디어

1. 월-일을 모두 Days (일) 로 통일

1월 1일-> 1

12월 31일 -> 365

로 치환한다.

 

이를 위해 HashMap 을 생성하여 각 월마다 일수를 매핑시켜주었다.

 

private final HashMap<Integer,Integer> monthDayMap = new HashMap<Integer, Integer>();
{
    monthDayMap.put(0, 0);
    monthDayMap.put(1, 31);
    monthDayMap.put(2, 28);
    monthDayMap.put(3, 31);
    monthDayMap.put(4, 30);
    monthDayMap.put(5, 31);
    monthDayMap.put(6, 30);
    monthDayMap.put(7, 31);
    monthDayMap.put(8, 31);
    monthDayMap.put(9, 30);
    monthDayMap.put(10, 31);
    monthDayMap.put(11, 30);
    monthDayMap.put(12, 31);
   	// 6월 15일이라면 31일(1월) + 28일(2월) + 31일(3월) + 30일(4월) + 31일(5월) + 15일
}

 

2. 3월 1일과 11월 30일 표현

항상 꽃이 피어있어야 하는 시작 - 종료 일을 일자로 표현해보자.

3월 1일: 31일 (1월) + 28일 (2월) + 1일 

11월 30일: 365일 - 31일 (12월) 

 

부등호에 유의하자.

첫 꽃의 개화일자는 반드시 3월 1일 이하(<=)여야한다.

마지막 꽃의 지는 일자는 11월 30일을 초과(>)해야한다.

 

3. 개화일은 오름차순, 낙화일은 내림차순 정렬한다.

꽃을 가장 적게 선택하는 최선의 방법은 개화일은 빠르고, 낙화일은 최대한 늦는 것이다.

만약 코딩 테스트에서 이런 문제를 만났다면, 직관적으로 위와 같은 생각을 하고 그리디로 접근해 풀어봐야겠다는 생각이 들어야한다.

 

 

다음 꽃을 선택할 수 없으면
0 으로 처리해야한다.

다음 개화일이 최근 선택한 꽃의 낙화일보다 같거나 낮은 꽃이 없는 경우 loop 을 탈출하여 0으로 답을 처리해야한다.

또 이미 한 번 선택한 꽃은 다시 선택할 수 없으므로 제외해야한다.

 

 

🔑 Java Code

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.Arrays;

import java.util.HashMap;

class Flower implements Comparable<Flower> {
    public int startDays = 0;
    public int endDays = 0;
    private final HashMap<Integer,Integer> monthDayMap = new HashMap<Integer, Integer>();
    {
        monthDayMap.put(0, 0);
        monthDayMap.put(1, 31);
        monthDayMap.put(2, 28);
        monthDayMap.put(3, 31);
        monthDayMap.put(4, 30);
        monthDayMap.put(5, 31);
        monthDayMap.put(6, 30);
        monthDayMap.put(7, 31);
        monthDayMap.put(8, 31);
        monthDayMap.put(9, 30);
        monthDayMap.put(10, 31);
        monthDayMap.put(11, 30);
        monthDayMap.put(12, 31);
    }

    Flower(int startMonth, int startDay, int endMonth, int endDay) {
        for (var month = 0; month < startMonth; month++) {
            this.startDays += monthDayMap.get(month);
        }
        this.startDays += startDay;

        for (var month = 0; month < endMonth; month++) {
            this.endDays += monthDayMap.get(month);
        }
        this.endDays += endDay;
    }

    @Override
    public int compareTo(Flower o) {
        if (this.endDays == o.endDays) return this.startDays - o.startDays;
        return o.endDays - this.endDays;
    }

}

public class Main {
    public static void main(String[] args) throws IOException {
        var bufferedReader = new BufferedReader(new InputStreamReader(System.in));
        var flowerCnt = Integer.parseInt(bufferedReader.readLine());

        var flowers = new Flower[flowerCnt];

        for (var i = 0; i < flowerCnt; i++) {
            var strs = bufferedReader.readLine().split(" ");
            flowers[i] = new Flower(Integer.parseInt(strs[0]), Integer.parseInt(strs[1]), Integer.parseInt(strs[2]), Integer.parseInt(strs[3]));
        }

        Arrays.sort(flowers);

        // start day is not Feb 28, can on Mar 1
        var startDays = 31 + 28 + 1;
        final int endDays = 365 - 31;

        var answer = 0;

        while (true) {
            var isExistFlower = false;
            for (var flower: flowers) {
                if (flower.startDays <= startDays) {
                    isExistFlower = true;
                    startDays = flower.endDays;
                    // if already choosen flower, doesn't choice more
                    flower.startDays = 400;
                    answer++;
                    break;
                }
            }

            if (!isExistFlower || startDays > endDays) break;
        }

        // if endDays not greater than 11 month 30
        if (startDays <= endDays) answer = 0;

        System.out.print(answer);

    }
}