TENSOR STUDIO
한 개의 회의실이 있는데 이를 사용하고자 하는 N개의 회의에 대하여 회의실 사용표를 만들려고 한다. 각 회의 I에 대해 시작시간과 끝나는 시간이 주어져 있고, 각 회의가 겹치지 않게 하면서 회의실을 사용할 수 있는 회의의 최대 개수를 찾아보자. 단, 회의는 한번 시작하면 중간에 중단될 수 없으며 한 회의가 끝나는 것과 동시에 다음 회의가 시작될 수 있다. 회의의 시작시간과 끝나는 시간이 같을 수도 있다. 이 경우에는 시작하자마자 끝나는 것으로 생각하면 된다.
입력
첫째 줄에 회의의 수 N(1 ≤ N ≤ 100,000)이 주어진다. 둘째 줄부터 N+1 줄까지 각 회의의 정보가 주어지는데 이것은 공백을 사이에 두고 회의의 시작시간과 끝나는 시간이 주어진다. 시작 시간과 끝나는 시간은 231-1보다 작거나 같은 자연수 또는 0이다.
출력
첫째 줄에 최대 사용할 수 있는 회의의 최대 개수를 출력한다.
2 초 128 MB
11
1 4
3 5
0 6
5 7
3 8
5 9
6 10
8 11
8 12
2 13
12 14
4
나는 이거 좀 어려웠다. 개인적으로 흔한 골드 문제보다도 어려웠던 것 같은데, 왜냐하면 그리디로 풀어야 하나? 하고 돌려봤더니 답이 안나와서 DP로 도전하다 다시 그리디로 돌아왔기 때문이다.
처음에는 회의 시작 시간 기준으로 그리디를 적용했으나, 정답이 나오지 않았다. 그리디의 특성상 최소단위로 나눈 작업의 결과가 항상 최적이라는 보장이 없기 때문에 그렇다. 이런 경우에는 작업을 나누는 기준이 잘못되었거나/그리디로 해결할 수 있는 문제가 아닌 경우가 많다. 아니면 기준/정렬이 잘못되었거나.
이 문제의 경우에는 회의가 끝나는 시간을 기준으로 정렬해서 그리디를 적용해야 풀이가 가능했다. 다음은 시작시간, 끝시간을 입력으로 받아서 튜플을 (끝시간, 시작시간)으로 저장한 예시 코드이다.
conference_number = int(input())
conference_list = []
for _ in range(conference_number) :
first, second = map(int, input().split())
conference_list.append((second, first))
conference_list.sort()
n = 0
answer = 0
for i, c in conference_list :
if n <= c :
answer += 1
n = i
print(answer)
다음은 위 코드를 자바 코드로, 정렬을 (끝시간, 시작시간) 으로 해 풀이한 것이 아니라 (시작시간, 끝시간)을 기준으로 정렬해 풀이한 코드이다.
package boj;
import java.lang.reflect.Array;
import java.util.ArrayList;
import java.util.Collections;
import java.util.Comparator;
import java.util.Scanner;
public class boj1931 {
public static void main(String[] args) {
Scanner scanner = new Scanner(System.in);
int conferenceNumber = scanner.nextInt();
ArrayList<int[]> conferenceList = new ArrayList<>();
for(int i = 0; i < conferenceNumber; i++) {
int[] temp = new int[2];
int start = scanner.nextInt();
int end = scanner.nextInt();
temp[0] = start;
temp[1] = end;
conferenceList.add(temp);
}
Collections.sort(conferenceList, new Comparator<int[]>() {
@Override
public int compare(int[] o1, int[] o2) {
if(o1[1] == o2[1]) {
return o1[0] - o2[0];
}else {
return o1[1] - o2[1];
}
}
} );
int n = 0;
int answer = 0;
for(int i = 0; i < conferenceList.size(); i++) {
if (n <= conferenceList.get(i)[0]) {
answer += 1;
n = conferenceList.get(i)[1];
}
}
System.out.println(answer);
}
}