백준 1931 : 회의실 배정

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

유명~한 문제이다.

근데 안풀어본 것 같아서

이참에 증명 과정도 알아보기로 했다.

 

일단 완전탐색을 하기에는... 지수 복잡도로 간다.

회의를 배정하냐 마냐를 선택해야하기 때문에 $O(2^n)$가 된다.

 

그러면 이제 그리디를 생각해볼 수 있겠는데,

1. 제일 짧은 것부터 고르기

2. 제일 먼저 끝나는 것부터 고르기

3. 제일 나중에 끝나는 것부터 고르기

 

뭐 사실 답이 2번이라는 건 알고 있었지만, 최소한 1번 3번의 반례와 2번이 정당한 이유를 제시하고 싶었다.

 

1번 반례

우선 1번의 반례를 제시해보겠다.

몇몇개의 블로그에서는 제일 짧은 것부터 고른다고 해서, 그 다음으로 짧은 게 선택 불가능하면 거기서 끝내버리는 예시를 제시했었다.

근데 내 생각에 가장 짧은 것부터라는 말에는 "(가능한 것 중)가장 짧은 것부터"라는 의미라고 생각한다.

그러니까 그 다음으로 짧은 게 선택 불가능 하더라도, 그 다음다음으로 짧은 게 선택 가능하면 선택하는 방식을 의미한다.

 

그러니까 이렇게 가장 왼쪽 것만 선택하는 게 아니라, 가장 오른쪽 것도 선택한다는 의미

 

아무튼 반례는 간단한데, 어렵게 생각해서 좀 헤맸다.

 

짧은 것부터 고르면, 하나 밖에 선택하지 못한다.

 

이렇게 짧은 걸 선택하느라 2개를 선택하지 못하게 되는 경우가 있을 수 있다.

 

3번 반례

3번은 반례가 너무 명확하다.

가장 먼저 시작하는 회의의 시작시간이 가장 빠른 시간이고, 종료시간이 가장 늦은 시간이면 걔 밖에 할당할 수가 없다.

이게 진짜 탐욕이 아닐까?

 

2번 증명

자 그럼 2번에 대한 증명을 해보자.

 

단순히 말로 설명하자면,

가장 먼저 끝나는 것을 고르는 것이, 그 이후에 회의를 배정할 시간이 제일 많이 남는 방법이기 때문이다.

 

복잡하게 말로 설명하자면,

회의를 배정하는 가장 "최적의 답"이 존재한다고 하자.

이때, 우리의 "먼저 끝나는 회의부터 배정 방법이 도출하는 답"(이하 우리의 답)과 이 "최적의 답"을 비교해보자.

 

1. 가장 먼저 끝나는 회의

"최적의 답"에서 가장 먼저 끝나는 회의보다,

"우리의 답"에서 가장 먼저 끝나는 회의가

더 먼저 끝나거나 최소한 같은 시간에 끝날 것이다(그것이 "먼저 끝나는 회의부터 배정" 방법이 보장하는 것)

가장 먼저 끝나는 회의 비교

 

2. x-1번째로 끝나는 회의

마찬가지로,

"최적의 답"에서 x-1번째로 끝나는 회의보다,

"우리의 답"에서 x-1번째로 끝나는 회의가

더 먼저 끝나거나 최소한 같은 시간에 끝날 것이다(위와 같음. "먼저 끝나는 회의부터 배정"했기 때문에)

x-1 번째로 끝나는 회의 비교

 

3. x번째로 끝나는 회의

(가정)

그렇다면 이때,

"최적의 답"에서 x번째로 시작하는 회의가

"우리의 답"에서 x번째로 시작하는 회의보다 먼저 끝날까?

 

(모순)

만약 그렇다고 해보자.

그러면 "우리의 답"이 "먼저 끝나는 회의부터 배정"한 것이 아니게 된다

 

왜냐하면,

만약 "최적의 답"에서 x번째로 시작하는 회의가

"우리의 답"에서 x번째로 시작하는 회의보다 먼저 끝나는 회의라면,

"우리의 답"은 "최적의 답"에서 x번째로 시작하는 그 회의를 선택했을 것이기 때문이다.

최적의 답의 x번째보다 늦으면, "먼저 끝나는 회의부터 배정"한 것이 아님

 

(결론)

따라서 "최적의 답"에서 x번째로 시작하는 회의가

"우리의 답"에서 x번째로 시작하는 회의보다 먼저 끝난다는 가정이 틀렸으므로,

"우리의 답"에서 x번쨰로 시작하는 회의가 더 먼저 끝나거나 최소한 같은 시간에 끝난다.

 

4. 결론

따라서,

"우리의 답"은

1번째로 끝나는 회의던, 2번째로 끝나는 회의던, ... , x-1번째로 끝나는 회의던, x번째로 끝나는 회의던,

... , 마지막으로 끝나는 회의던 상관없이

"최적의 답"에서의 회의보다 항상 먼저 끝나거나 최소한 같은 시간에 끝난다.

 

그러면, "최적의 답"보다 "우리의 답"이 더 많은 시간을 남기며 끝나거나 최소한 같은 시간을 남기며 끝난다.

"최적의 답"이라는 의미상, "우리의 답"이 더 좋은 방법일 순 없으므로, "최적의 답"은 "우리의 답"과 같다.

 

2번 방법에 대한 코드

N = int(input())
times = []
for i in range(N):
  times.append(tuple(map(int, input().split())))

times.sort(key=lambda x : (x[1],x[0]))

lastEndTime = -1
count = 0
for i in range(N):
  if times[i][0] >= lastEndTime:
    lastEndTime = times[i][1]
    count += 1
print(count)

 

새롭게 배운 점

• sorted와 sort의 차이
• sort에서 tuple을 2가지 기준으로 정렬하는 방법

트러블 슈팅

• if문에서 비교시, 등호를 넣지 않았음
• 정렬 시, 시작 시간도 정렬이 필요하다는 사실을 몰랐음