[python]백준 1931번: 회의실 배정(그리디 알고리즘)

# 1931 회의실 배정

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

1931번: 회의실 배정

 

풀이

N = int(input())
list_ = []

for i in range(N):
  a,b = map(int, input().split()) # 시작시간, 끝나는 시간
  list_.append([a,b])

list_.sort(key=lambda x:(x[1], x[0])) # 끝나는 시간을 기준으로 정렬, 시작 시간을 기준으로 정렬

last = 0
count = 0
for i, j in list_: # 시작과 끝 시간
  if i >= last: # 끝나는 시간보다 시작시간이 클 경우
    count += 1 # 조건이 성립하면 카운트
    last = j  # 핵심코드, 끝나는 시간을 last에 기록
print(count)

해설

그리디 알고리즘으로 성립 조건을 잘 생각해보는게 중요하다. 정해진 시간 안에 회의실을 가장 배정을 많이하려면 다음과 같은 조건이 필요할 것이다.

 

1. 회의 시간이 짧을수록 많이 배정할 수 있다.

2. 빨리 시작해야 한다.

3. 가장 적게 겹쳐야 한다.

4. 회의가 빨리 끝나야 한다.

 

1번의 조건으로 정렬을 하게 된다면 아래와 같은 상황에서 오류가 생긴다. b가 가장 회의시간이 짧다. b를 선택하지 않으면 a와 c를 배정할 수 있지만  b를 선택하면 1개를 배정하게 된다. 

2번 조건 정렬 또한 a가 시작시간이 가장 빠르지만 회의 2개를 잡지 못하게 되기 떄문에 count가 제대로 되지 않는다.

3번에 대한 반례는 잘 모르겠다. 하지만 직관적으로 3번보다는 4번으로 정렬하는 방법이 더 쉬울것 같다는 생각이 들어서 4번으로 접근했다.

 

회의가 빨리 끝날수록 이후 시간에 회의할 수 있는 시간이 많아진다. 그렇기 때문에 끝나는 시간을 기준으로 정렬을 해야한다.  정렬의 방법으로는 lambda를 썼으며, 끝나는 시간 x[1]을 기준으로 오름차순, 시작하는 시간 x[0]을 기준으로 오름차순 정렬했다.

list_.sort(key=lambda x:(x[1], x[0])) # 끝나는 시간을 기준으로 정렬, 시작 시간을 기준으로 정렬

그 이후에는 for문을 통해 시작시간(i)과 끝나는 시간(j)을 체크해준다.

last = 0
count = 0
for i, j in list_: # 시작과 끝 시간
  if i >= last: # 끝나는 시간보다 시작시간이 클 경우
    count += 1 # 조건이 성립하면 카운트
    last = j  # 핵심코드, 끝나는 시간을 last에 기록
print(count)

last와 count를 0으로 세팅하고, i가 last보다 클 경우에는 count를 해주는 로직을 작성했다. 이 로직이 성립하는 이유는 우리가 빨리 끝날수록 회의를 할 수 있는 시간이 많아진다는 조건이 성립하기 때문이며, 이 조건을 위해 끝나는시간(숫자)을 오름차순으로 정렬했다.

 

i(시작시간)가 last값보다 크거나 같다면 회의실을 사용할 수 있으므로 조건이 성립하므로 count에 +1을 해주고 last를 끝나는 시간으로 저장해준다. 이 과정을 반복하고 count를 출력해주면 회의를 사용할 수 있는 최댓값이 나오게 된다.