[Java] JUNGOL1828: 냉장고

 1828 : 냉장고

제한시간1000 ms    메모리제한32 MB

 

문제

N개의 화학 물질 C1, C2, …, Cn이 있다. 

이들 각각은 보관되어야 할 온도가 각기 다른데, 각 Ci마다 최저 보관 온도 xi와 최고 보관 온도 yi가 정해져 있다. 

즉 Ci는 온도 xi이상, yi이하의 온도에서 보관되어야만 안전하다.

이 화학 물질들을 모두 보관하기 위해서는 여러 대의 냉장고가 필요한데 가능하면 적은 수의 냉장고를 사용하고 싶다. 

이를 해결하는 프로그램을 작성하시오.

 

입력형식

첫줄에 화학물질의 수 N이 입력된다. N의 범위는 1이상 100 이하이다. 

두 번째 줄부터 N+1줄까지 최저보관온도와 최고보관온도가 입력된다. 

보관온도는 -270° ~ 10000°이며, 각 냉장고는 임의의 정해진 온도를 일정하게 유지할 수 있고, 냉장고는 아주 크다고 가정한다.

 

출력형식

첫줄에 최소로 필요한 냉장고의 대수를 출력한다.

 

풀이

그리디한 방법으로 풀이해야합니다.

활동 선택 문제(Activity-Selection)의 경우 이중 배열을 하나의 기준으로 정렬하고 또 값이 같을 때 2차 정렬을 할 수 있음에 주의합니다.

import java.util.*;

public class Main {
	static int N,cnt = 0, arr[][];
	
	static void dfs(int depth, int maxC) {
		if(depth==N) { // N에 도달하면 종료
			return;
		}
		if(arr[depth][0]>maxC) { // 온도 범위 끝값보다 커질 때 새로 냉장고 생성
			cnt++;
			dfs(depth+1, arr[depth][1]); // 현재 화학물질 기준 온도 끝값 설정
		}else {
			dfs(depth+1, Math.min(maxC,arr[depth][1])); // 범위 안이라면 다음으로
		}
	}
	public static void main(String[] args) {
		Scanner sc = new Scanner(System.in);
		N = sc.nextInt();
		arr = new int[N][2];
		
		for(int i=0; i<N; i++) {
			arr[i][0] = sc.nextInt();
			arr[i][1] = sc.nextInt();
		}
		
		Arrays.sort(arr, new Comparator<int[]>(){

			@Override
			public int compare(int[] o1, int[] o2) {
				return o1[1]==o2[1]?o1[0]-o2[0]:o1[1]-o2[1];
			} //최대 온도로 오름차순 정렬, 같은 경우 최소 온도 오름차순
			
		});

		dfs(0,-271);
		System.out.println(cnt);
}
}