Baekjoon1931*: 회의실 배정, 시간 초과와 그리디 알고리즘

Baekjoon1931*: 회의실 배정, 시간 초과와 그리디 알고리즘

문제

한 개의 회의실이 있는데 이를 사용하고자 하는 N개의 회의에 대하여 회의실 사용표를 만들려고 한다. 각 회의 I에 대해 시작시간과 끝나는 시간이 주어져 있고, 각 회의가 겹치지 않게 하면서 회의실을 사용할 수 있는 회의의 최대 개수를 찾아보자. 단, 회의는 한번 시작하면 중간에 중단될 수 없으며 한 회의가 끝나는 것과 동시에 다음 회의가 시작될 수 있다. 회의의 시작시간과 끝나는 시간이 같을 수도 있다. 이 경우에는 시작하자마자 끝나는 것으로 생각하면 된다.

입력

첫째 줄에 회의의 수 N(1 ≤ N ≤ 100,000)이 주어진다. 둘째 줄부터 N+1 줄까지 각 회의의 정보가 주어지는데 이것은 공백을 사이에 두고 회의의 시작시간과 끝나는 시간이 주어진다. 시작 시간과 끝나는 시간은 2^31-1보다 작거나 같은 자연수 또는 0이다.

출력

첫째 줄에 최대 사용할 수 있는 회의의 최대 개수를 출력한다.

풀이1

제한조건을 확인한다. 시작시간과 끝나는 시간의 최대 간격은 2의 31승으로 매우 커보이지만 int의 최대범위다. 회의의 수는 10만까지 가능하고 주어진 회의시간들은 오름차순 또한 아니다.

동적계획법을 활용하여 매 항마다 최대 회의시간을 기록한다. 현재항 i에서 자기보다 이전항 중 시간이 겹치지 않는 회의를 찾는다.

시간이 겹치지 않는 회의 중 최대값을 가져와 1을 더한다

1 4 1 3 5 1 0 6 1 5 7 2 3 8 1 5 9 2

import java.util.Scanner; public class Main { public static void main(String[] args){ Scanner sc = new Scanner(System.in); int N = sc.nextInt(); int[][] dp = new int[N+1][3]; dp[0][2]=0; for(int i=1;i=dp[j][1] || dp[i][1]<=dp[j][0]) { dp[i][2]=Math.max(dp[i][2], dp[j][2]+1); }}} System.out.print(dp[N][2]); }}

*시간 초과가 나온다. 이러한 동적 계획법을 보완하기 위해 그리디 알고리즘을 사용한다고 한다.

풀이2

그리드 알고리즘의 활동 선택 문제(Activity Selection problem) 유형이다. 위와 같이 동적계획법을 통해 최대값을 계속 구해나가며 구할 수 있지만 시간이 오래걸린다는 단점이 존재한다. 이를 더 단순화하기 위해 회의가 가장 먼저 끝나는 순서대로 정렬한 뒤 회의들을 이어 붙이는 식으로 한다.

[ 가장 먼저 끝나는 회의를 선택 ] →[ 그 뒤에 겹치지 않으면서 가장 먼저 끝나는 회의를 선택 ]을 반복하는 것이다.

이를 위해 정렬을 해야하는데, 이중배열의 정렬은 Arrays.sort의 compare을 사용한다.

정렬을 한 후에는 이미 시간 순으로 나열되어있기 때문에 반복문을 한 번 돌리면서 값을 구할 수 있게 된다.

import java.util.*; public class Main { public static void main(String[] args){ Scanner sc = new Scanner(System.in); int N = sc.nextInt(); int[][] arr = new int[N][2]; int sum=0; int left=0; for(int i=0; i { //정렬하는 코드 if(o1[1] == o2[1]) { return Integer.compare(o1[0],o2[0]);} else{ return Integer.compare(o1[1],o2[1]); } }); for(int i=0; i=left) { //어차피 끝나는 시간 순차적으로 배열되어있기 때문에 left=arr[i][1]; //오른쪽으로 가면서 겹치지 않는 구간을 만나면 바로 추가해준다 sum++; } } System.out.print(sum); }}

from http://devyoseph.tistory.com/129 by ccl(A) rewrite - 2021-11-01 03:28:08