[백준] 2457. 공주님의 정원 (Java)

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

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일까지 매일 꽃이 한 가지 이상 피어 있도록,

선택한 꽃들의 최소 개수를 출력하는 프로그램을 작성하시오. 

---

💡 아이디어

여기서 사용되는 날짜를 모두 일수를 만들어 계산하기 편하게 만듭니다.

1월 1일 -> 1일

2월 1일 -> 32일

12월 31일 -> 365일

---

 

📖 풀이과정

1. 꽃의 개화시기와 낙화시기를 일수로 바꿔서 flower배열에 저장해 줍니다.

s=br.readLine().split(" ");

flower[i][0]=changeToDay(Integer.parseInt(s[0]),Integer.parseInt(s[1]));
flower[i][1]=changeToDay(Integer.parseInt(s[2]),Integer.parseInt(s[3]));

 

2. flower을 개화시기 순, 피어있는 기간이 긴 순으로 정렬합니다.

 

3. 3월 1일을 현재 날짜라고 저장하고, 현재 날짜에 피어있는 꽃 중에서 낙화시기가 가장 긴 꽃을 선택합니다.

(현재 날짜에서 피어있는 기간이 가장 긴 꽃을 선택하면, 꽃을 최소한으로 사용할 수 있습니다.)

4. 꽃을 정했다면 해당 꽃의 낙화시기를 현재 날짜에 저장해 주고, 3번 과정과 같이 다음 꽃을 결정합니다.

(만약 꽃이 피어있는 시기가 이어지지 않는다면 0을 출력하고, 더 이상 다음 꽃을 계산하지 않습니다.)

 

5. 3-4 과정을 반복해 꽃을 최소한으로 사용한 개수를 출력합니다.

---

전체 코드

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

public class BJ2457_공주님의정원 {

	public static void main(String[] args) throws Exception{
		// TODO Auto-generated method stub

		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		int n = Integer.parseInt(br.readLine());
		
		int start = changeToDay(3,1);
		int end = changeToDay(11,30);
		System.out.println(start+" "+end);
		
		String[] s;
		
		int[][] flower = new int[n][2];//개화시기,낙화시기
		for(int i=0;i<n;i++) {
			s=br.readLine().split(" ");
			
			flower[i][0]=changeToDay(Integer.parseInt(s[0]),Integer.parseInt(s[1]));
			flower[i][1]=changeToDay(Integer.parseInt(s[2]),Integer.parseInt(s[3]));
		}
		//개화시기 순, 피어있는 기간이 긴 순으로 정렬
		Arrays.sort(flower,new Comparator<int[]>() {
			public int compare(int[] a, int[] b) {
				if(a[0]==b[0]) return (b[1]-b[0])-(a[1]-b[0]);
				else return a[0]-b[0];
			}
		});
		
		int now=start;//현재 날짜(일)
		int cnt=0;//최소한의 꽃 개수
		while(now<=end) {
			int maxEnd=-1;//낙화 시기가 가장 뒤인 꽃
			for(int i=0;i<flower.length;i++) {
				if(flower[i][0]<=now && flower[i][1]>now && flower[i][1]>maxEnd)
					maxEnd=flower[i][1];
			}
			//이어지는 꽃이 없다면 0 출력.
			if(maxEnd==-1) {
				System.out.println(0);
				return;
			}
			cnt++;
			now=maxEnd;
		}
		
		System.out.println(cnt);
		
	}
    //날짜 -> 일자
	static int changeToDay(int mm, int dd) {
		
		int day=dd;
		mm-=1;
		while(mm>0) {
			if(mm==1 || mm==3 || mm==5 || mm==7 || mm==8 || mm==10 || mm==12)
				day+=31;
			else if(mm==2)
				day+=28;
			else
				day+=30;
			mm--;
		}
		return day;
	}
}