[백준][Python] 1931번 회의실 배정 - DP

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

1931번: 회의실 배정

 

Python

import sys
input = sys.stdin.readline

n = int(input())
arr = [list(map(int, input().split())) for _ in range(n)]
arr = sorted(arr, key=lambda x: (x[1], x[0]))

end = [0]
for i in range(n):
    if arr[i][0] >= end[-1]:
        end.append(arr[i][1])

print(len(end)-1)

 

 

풀이

• 원소를 종료 시간대를 기준으로 정렬
  • sorted 함수에 람다함수로 정렬 시 기준이 되는 원소의 순서를 정할 수 있다
  • 현재 1번째 원소가 우선적으로 적용되어 정리된 후, 같은 값에 대해 0번째 원소를 기준으로 정렬하게 했다.
• end 리스트는 dp 용으로 쓰기 위한 리스트다
  • 인덱스를 각 횟수, 원소를 그 횟수일 때 가장 작은 종료 시각을 넣어둔다.
  • 위에서 종료 시각을 기준으로 정렬했기에 이후에 더 빨리 끝나는 종료 시각은 없다.
  • 그래서 end 리스트의 마지막 원소보다 늦게 시작하는 것만 확인하면 된다.
  • 각 횟수가 인덱스를 의미하기에 출력은 전체 리스트 길이를 출력한다. -1은 0번일 때를 제외하여 계산.

 

1 4	[0, 4]
3 5	[0, 4]  3시는 저장된 4시보다 빠르기에 불가능
0 6	[0, 4]. 0시는 저장된 4시보다 빠르기에 불가능
5 7	[0, 4, 7]
3 8	[0, 4, 7]  3시는 저장된 7시보다 빠르기에 불가능
5 9	[0, 4, 7]  5시는 저장된 7시보다 빠르기에 불가능
6 10	[0, 4, 7]  6시는 저장된 7시보다 빠르기에 불가능
8 11	[0, 4, 7, 11]
8 12	[0, 4, 7, 11] 12시는 저장된 11시보다 빠르기에 불가능
2 13	[0, 4, 7, 11]  2시는 저장된 11시보다 빠르기에 불가능
12 14	[0, 4, 7, 11, 14]

 

 

이 방법의 장점은 가장 많은 회의를 할 때 걸린 시간도 알 수 있다.