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

문제 설명

오늘은 공주님이 태어난 경사스러운 날이다. 왕은 이 날을 기념하기 위해 늘 꽃이 피어있는 작은 정원을 만들기로 결정했다.

총 N개의 꽃이 있는 데, 꽃은 모두 같은 해에 피어서 같은 해에 진다. 하나의 꽃은 피는 날과 지는 날이 정해져 있다. 예를 들어, 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개의 꽃들 중에서 위의 두 조건을 만족하는, 즉 3월 1일부터 11월 30일까지 매일 꽃이 한 가지 이상 피어 있도록 꽃들을 선택할 때, 선택한 꽃들의 최소 개수를 출력하는 프로그램을 작성하시오. 

문제 풀이

이 문제의 핵심은 날짜를 어떻게 처리하느냐입니다.

저는 처음에 월, 일, 월, 일로 나누어 생각을 했으나 단순히 날짜의 비교만 하면 해결할 수 있으므로 월*100+일 로 처리하였습니다.

 

그 이후 처음 date를 301(3월1일)로 잡고 1130(11월30일)과 작거나 같은 경우 반복을 통해  꽃이 피고 지는 기간이 date를 포함하고 있을 때 꽃이 지는 마지막 날짜가 date보다 큰 경우 date에 넣어주었습니다.

 

findDate와 index를 추가한 이유는 index의 경우 N=3, 1/10~4/30, 4/30~8/30, 8/23~8/28 일 때 반복문을 돌 때 2번째 위치에서 무한 루프가 되는 것을 막기 위함이고findDate의 경우 1130에 도달하지 못하고 적합한 꽃을 찾지 못하여 while이 종료되었을 때 답을 0으로 출력하기 위함입니다.

풀이 코드

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

class BOJ2457 {
    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        int N = Integer.parseInt(br.readLine());
        int[][] flowers = new int[N][2];

        for(int i=0; i<N; i++){
            StringTokenizer st = new StringTokenizer(br.readLine());
            for(int j=0; j<2; j++)
                flowers[i][j] = Integer.parseInt(st.nextToken())*100+Integer.parseInt(st.nextToken());
        }

        Arrays.sort(flowers, (f1, f2) -> {
           if(f1[0] != f2[0]) return f1[0] - f2[0];
           return f1[1] - f2[1];
        });

        int ans = 0, date = 301, findIndex = -1;
        while(date <= 1130){
            boolean findDate = false;
            int maxDate = date;
            for(int i=findIndex+1; i<N; i++){
                if((flowers[i][0] <= date && date <= flowers[i][1] && maxDate < flowers[i][1])) {
                    maxDate = flowers[i][1]; findDate = true;
                    findIndex = i;
                }
            }
            if(!findDate) break;
            ans+=1; date = maxDate;
        }

        if(date <= 1130) System.out.println(0);
        else System.out.println(ans);
    }
}

 

<출처>

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

2457번: 공주님의 정원