[Java] Baekjoon19621: 회의실 배정 2

회의실 배정 2

1 초

256 MB

626

323

245

50.515%

문제

서준이는 아빠로부터 N개의 회의와 하나의 회의실을 선물로 받았다. 각 회의는 시작 시간, 끝나는 시간, 회의 인원이 주어지고 한 회의실에서 동시에 두 개 이상의 회의가 진행될 수 없다. 단, 회의는 한번 시작되면 중간에 중단될 수 없으며 한 회의가 끝나는 것과 동시에 다음 회의가 시작될 수 있다. 회의의 시작 시간은 끝나는 시간보다 항상 작다. N개의 회의를 회의실에 효율적으로 배정할 경우 회의를 진행할 수 있는 최대 인원을 구하자.

입력

첫째 줄에 회의의 수 N이 주어진다. 둘째 줄부터 N + 1 줄까지 공백을 사이에 두고 회의의 시작시간, 끝나는 시간, 회의 인원이 주어진다.

출력

첫째 줄에 회의실에서 회의를 진행할 수 있는 최대 인원을 출력한다.

제한

• 1 ≤ N ≤ 25
• 임의의 회의 K(1≤ K ≤ N)는 회의 K − 1과 회의 K + 1과는 회의 시간이 겹치고 다른 회의들과는 회의 시간이 겹치지 않는다.
• 모든 회의의 시작 시간과 끝나는 시간은 2^31 − 1보다 작거나 같은 자연수 또는 0이다.
• 모든 회의의 시작 시간과 끝나는 시간은 서로 다르다.
• 회의 인원은 1,000보다 작거나 같은 자연수 이다.

풀이

K <= N <= 25 므로 입력값은 100개를 넘지 않습니다. 맘 편하게 Scanner를 사용했습니다.

회의실을 최대한 많이 선택한다고 해서 인원수가 최대가 되는 것은 아니었습니다.

즉 현재보다 늦게 시작하지만 인원수가 더 많은 회의가 존재할 수 있으므로 브루트 포스 기법으로 풀이했습니다.

 

부분집합으로 구하기

dfs 를 이용해 부분집합으로 구현했습니다.

회의 정보를 배열에 받아주고 배열의 인덱스 0부터 시작합니다.

그리고 현재 회의를 선택하거나, 선택하지 않거나 결정한 뒤 다음 인덱스로 넘어갑니다.

import java.util.Arrays;
import java.util.Comparator;
import java.util.Scanner;

public class Main {
	static int N,MAX,arr[][]; //시작, 끝, 인원
	
	static void dfs(int idx,int end, int sum) {
		
		if(idx == N) {
			MAX = Math.max(MAX, sum);
			return;
		}
		
		if(arr[idx][0]>=end) {
			dfs(idx+1,arr[idx][1],sum+arr[idx][2]); //현재 회의 선택
		}
		dfs(idx+1,end,sum); //현재 회의 선택X
	}
	public static void main(String[] args) {
		Scanner sc = new Scanner(System.in);
		N = sc.nextInt();
		arr = new int[N][3];
		for(int i=0; i<N; i++) {
			arr[i][0] = sc.nextInt();
			arr[i][1] = sc.nextInt();
			arr[i][2] = sc.nextInt();
		}
		Arrays.sort(arr, new Comparator<int[]>() {

			@Override
			public int compare(int[] o1, int[] o2) {
				
				return o1[1]-o2[1];
			}
		});
		
		dfs(0,0,0);
		System.out.println(MAX);
}
}