[Java] 백준 1931.회의실 배정

➡️문제 링크

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

 

 

💡아이디어

사실 이 문제 예전부터 몇 번 풀어서 "그리디"로 풀어야 한다는 걸 알고 있었다

하지만 "왜"가 중요하므로 다시 차근차근 접근해, 우선은 그리디는 배제하고 스스로 생각해봤다.

우선, 문제에서 "겹치지 않게 최대한 많이" 라는 조건을 보고, 처음부터 알차게 사용을 해야 한다고 생각했고

그러기 위해서는 "정렬"을 해야한다고 생각했다.

 

그렇다면 시작시간? 끝나는 시간?  둘 중에 무엇을 기준으로 정렬할까?

이 부분에 대해 헷갈려 우선 시작시간을 기준으로 정렬해봤다

(0, 6)을 선택했을 때는 (6, 10) -> (12, 14) 이렇게 총 3번 회의실을 사용할 수 있다.

그렇다면 이게 최적의 값, 최대 사용 횟수 일까? 

(1, 4)를 선택한다면, (5, 7), (8, 11), (12, 14), 총 4번 사용할 수 있다.

즉, 시작하는 시각 오름차순 정렬은 최적의 값을 보장해주지 않는다.

그래서 결국 완탐을 하며 최적의 값을 찾아야 했고, 결과는 시간초과!

 

이번에는 끝나는 시각을 기준으로 오름차순 정렬해보자.

첫 번째 원소를 선택한다면,

(1, 4), (5, 7), (8, 11), (12, 14), 총 4번 사용할 수 있다.

그래도 해봐야 하는 거 아니야?라는 생각이 들 수 도 있지만,

(3, 5) -> (5, 7) -> (6, 10) -> (12, 14) / (0, 6) -> 6, 10) -> (12, 14)... 등

결국 최댓값을 보장해준다.

시작하는 시간 기준 오름차순 정렬	끝나는 시간 기준 오름차순 정렬
0 6 1 4 2 13 3 5 3 8 5 7 5 9 6 10 8 11 8 12 12 14	1 4 3 5 0 6 5 7 3 8 5 9 6 10 8 11 8 12 2 13 12 14

 

 

 

✏️문제 풀이

1. 완탐 - 오답 (시간초과)

정렬 기준을 알았고

현재 시작하는 시간이 이전에 끝난값과 같거나 커야 한다는 것도 알았다.

근데 어떻게 구현해야 할 지 고민됐다.

일단 돌리고보자 생각해서 완탐을 했다.

예제 케이스는 정답이지만, 결과는 시간초과

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

public class Main {
	static int N;
	static List<int []> room = new ArrayList<>();
	static int result = 0;
	public static void main(String[] args) throws IOException{
		// TODO Auto-generated method stub
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		N = Integer.parseInt(br.readLine());

		for(int i = 0; i < N; i++) {
			StringTokenizer st = new StringTokenizer(br.readLine());
			int start = Integer.parseInt(st.nextToken());
			int end = Integer.parseInt(st.nextToken());
			room.add(new int[] {start, end});
		}
		
		// 정렬 (끝, 시작 시간 오름차순)
		Collections.sort(room, (a, b)-> {
			if(a[1] == b[1]) return a[0] - b[0];
			else return a[1] - b[1];
		});
		
		// 회의의 최대 개수 찾기
		solve(0, 0, 0);
		
		// 정답 출력
		System.out.println(result);
	
	}
	
	static void solve(int idx, int curEnd, int curCount) {
		for(int i = idx; i < N; i++) {
			int [] cur = room.get(i);
			if(cur[0] >= curEnd) {	// i번째 사용 가능
				solve(i+1, cur[1], curCount+1);
			}
		}
		
		result = Math.max(result, curCount);
		return;
	}
	

}

 

 

2. 그리디- 성공

시간초과가 발생한다는 건, 위의 재귀가 되는 solve() 호출이 문제다.그러면 완탐이 접근법이 아니다는 건 땅땅땅.그렇다면, 완탐으로 이리저리 값을 저울질 하지 않고도 현재 값이 답이 될수도 있다는건데,"만약에, 지금 선택한 값보다 그 다음 인덱스, 그 다다음 인덱스를 선택했을 때 최댓값이 나올수도 있지 않나?"라는 생각이 들었다.

 

그러다, "정렬"이 그 최댓값을 보장해준다고 깨달았다.정렬을 "끝나는 시각"을 기준으로 했기 때문에, 이제 선택하는 값에 대한 정당성(?)을 부여하는 것이었다.그래서 for문을 돌렸고, 결과는 성공!

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

public class Main { 
	public static void main(String[] args) throws IOException{
		// TODO Auto-generated method stub
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		int N = Integer.parseInt(br.readLine());
		List<int []> room = new ArrayList<>();
		
		for(int i = 0; i < N; i++) {
			StringTokenizer st = new StringTokenizer(br.readLine());
			int start = Integer.parseInt(st.nextToken());
			int end = Integer.parseInt(st.nextToken());
			room.add(new int[] {start, end});
		}
		
		// 정렬 (끝, 시작 시간 오름차순)
		Collections.sort(room, (a, b)-> {
			if(a[1] == b[1]) return a[0] - b[0];
			else return a[1] - b[1];
		});
		
		// 회의의 최대 개수 찾기
		int idx = 0;
		int preEnd = 0;	// 이전 타임 끝나는 시간
		int result = 0;
		
		for(int i = 0; i < N; i++) {
			int [] cur = room.get(i);	// 현재값
			
			if(cur[0] >= preEnd) {	// i번째 사용 가능
				preEnd = cur[1];	// 끝나는 시간 갱신
				result++;
			}
		}

		// 정답 출력
		System.out.println(result);
	
	}

}