/* 문제 */
한 개의 회의실이 있는데 이를 사용하고자 하는 N개의 회의에 대하여 회의실 사용표를 만들려고 한다. 각 회의 I에 대해 시작시간과 끝나는 시간이 주어져 있고, 각 회의가 겹치지 않게 하면서 회의실을 사용할 수 있는 회의의 최대 개수를 찾아보자. 단, 회의는 한번 시작하면 중간에 중단될 수 없으며 한 회의가 끝나는 것과 동시에 다음 회의가 시작될 수 있다. 회의의 시작시간과 끝나는 시간이 같을 수도 있다. 이 경우에는 시작하자마자 끝나는 것으로 생각하면 된다.
그리디 문제로 한 번의 실패 후 성공했다.
처음에는 회의 시간이 짧은 순서대로 정렬힌 후 가장 짧은 회의부터 회의실을 사용하도록 했다. 짧은 시간의 회의를 최대한 많이 포함해야 회의의 최대로 많이 할 수 있다고 생각했기 때문이다.
# 틀린 코드
n = int(input())
time = []
max_time = 0
count = 0
for i in range(n):
tem = list(map(int, input().split()))
time.append(tem)
if max_time < max(tem):
max_time = max(tem)
table = [0]*(max_time + 1)
time.sort(key=lambda x:x[1]-x[0])
for i in time:
dur = i[1] - i[0]
if table[i[0] : i[1]] == [0]*dur:
for k in range(dur):
table[i[0] + k] = 1
count += 1
print(count)
입력 받은 회의 시간 중 가장 늦게 끝나는 시간을 max_time에 저장해 그 길이만큼 시간표 리스트(table)을 만들어 0으로 채웠다. 앞에서 검토한 회의들이 사용하고 있는 시간에는 1로 변경해 다음 회의를 검토할 때 시간이 겹치는지 확인하기 위해서다.
그러나 이 방법은 항상 최적의 해를 구하지 못하는 방법이었다. 예를 들어 회의 시간이
8 10
7 9
9 11
11 12
이렇게 입력되었다면, 회의 시간에 따라 다음과 같이 정렬되어 계산되었을 것이다.
11 12 -> 회의실 사용 O
8 10 -> 회의실 사용 O
7 9 -> 회의실 사용 X
9 11 -> 회의실 사용 X
그러나 (11,12), (7,9), (9,11)이 회의실을 사용하는 것이 더 많은 회의를 할 수 있다. 가장 먼저 입력된 (8,10)이 (7,9)와 (9,11)을 사용할 수 없게 만들었다.
따라서 회의를 많이 진행하려면 단순히 짧은 회의를 먼저 집어넣는 방법으로는 해결할 수 없다.
이후에 생각한 방법은 일찍 끝나는 회의 순서대로 회의실을 사용하는 것이다. 앞선 예시에서 (7,9)가 (8,10)보다 먼저 검토되었다면 (7,9)가 선택되고, 이어서 (8,10)은 탈락한 후 (9,11)이 선택되었을 것이다. 지금 선택한 회의가 빨리 끝날수록 이어서 할 수 있는 회의의 수는 많아진다.
이 경우 고려해야 할 것은 같은 시간에 끝나는 회의들끼리의 정렬이다. (8,10), (9,10), (10,10)이 입력값으로 들어왔다고 생각해 보자. (8,10)과 (9,10)은 큰 문제가 되지 않는다. 둘 중 어느 것을 선택하든 다음 회의는 10시에 시작할 수 있는 회의들만 고려될 것이며, 이전 회의가 8시 전에 끝났다면 무엇을 선택하든 결과인 개수는 같기 때문이다. 문제는 (10,10)과 같이 시작과 동시에 끝나는 회의들이다. 만약 (10,10)이 저 셋 중 가장 처음으로 정렬되어 있다면 (8,10)과 (9,10)은 검토 과정에서 탈락할 것이다. 앞서 선택된 회의가 끝나는 시간 이후에 시작해야 선택될 수 있기 때문이다. 따라서 같은 시간에 끝나는 회의라면, 먼저 시작한 순서대로 정렬해야 한다.
/* 정답 코드 */
n = int(input())
time = []
for i in range(n):
time.append(list(map(int, input().split())))
time.sort(key=lambda x:x[0]) # 시작 시간 기준 정렬
time.sort(key=lambda x:x[1]) # 종료 시간 기준 정렬
count = 0 # 가능한 회의의 수
end_time = 0
for i in time:
if i[0] >= end_time:
count += 1
end_time = i[1]
print(i)
print(count)
원하는대로 정렬하려면 우선 시작 시간을 기준으로 정렬한 후 종료 시간을 기준으로 한 번 더 정렬한다. 이렇게 하면 종료 시간이 같은 경우 앞서 정렬한 순서가 그대로 지켜지므로 원하는대로 정렬할 수 있다.
찾아보니 내가 했던 두 개의 정렬문은
time.sort(key = lambda x: (x[1], x[0]))
이렇게 한 줄로 쓸 수 있었다.
그리디 문제는 아이디어가 중요하다. 현재 시점에서 최선의 선택을 하면 된다는 것은 알고 있지만 더 좋은 것이 무엇인지에 대한 기준을 내가 판단해야 한다. 이 문제에서 나는 짧은 회의일수록 좋은 선택이라고 생각했지만 실은 빨리 끝나는 회의일수록 좋은 선택이었다.
이 문제를 그리디 문제집이 아닌 곳에서 처음으로 봤다면 바로 그리디라고 판단할 수 있었을까?
여러 문제를 풀어보면서 아이디어를 빨리 생각해낼 수 있는 능력을 길러야겠다.
'Algorithm' 카테고리의 다른 글
[1541] 잃어버린 괄호 - Python (0) | 2023.02.09 |
---|---|
[11399] ATM - Python (0) | 2023.02.09 |
[11047] 동전 0 - Python (0) | 2023.02.08 |
그리디 - 현재 상황에서 가장 좋아 보이는 것만을 선택하는 알고리즘 (0) | 2023.02.08 |
[11053] 가장 긴 증가하는 부분 수열 - Python (0) | 2022.11.11 |