회의실 배정 [백준 1931번]

문제

 

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

1931번: 회의실 배정

 

내 풀이

 

그리디 알고리즘이다.

가장 먼저 끝나는 회의를 선택한 후, 그 회의를 기점으로 시작하는 시간이 금방 다가오는 회의를 선택하는 방법으로 풀었다.

 

여기서 중요한 것은 정렬이다.

끝나는 시간을 기준으로 오름 차순 정렬하고, 끝나는 시간이 같다면 시작하는 시간을 기준으로 오름 차순 정렬해야 한다.

"끝나는 시간으로만 정렬하면 안되나요?"라는 질문을 했을 때의 답변은 "안됩니다."이다.

 

2
3 3
1 3

의 예제를 생각해보자.

 

1. 끝나는 시간으로만 정렬하면 [(3, 3), (1, 3)]이 되기 때문에 답은 1이 된다.

2. 끝나는 시간 정렬 -> 시작하는 시간 정렬로 하면 [(1, 3), (3, 3)]이 되기 때문에 답은 2가 된다. 이 방법으로 해야지 회의를 더 많이 할 수 있다.

 

import sys
input = sys.stdin.readline

N = int(input())
meeting = [tuple(map(int, input().strip().split())) for i in range(N)]
meeting.sort(key=lambda x: (x[1], x[0]))
e, cnt = 0, 0
for m in meeting:
    if e <= m[0]:
        e = m[1]
        cnt += 1
print(cnt)

 

총평

그리디 알고리즘을 공부안 한지 너무 오래 돼서 개념을 다 까먹었다. 그래서 처음에 문제를 브루트 포스로 풀었다가 시간 초과 나서 틀렸었다. 그리디 알고리즘이라는 것을 인지하고 난 후 다시 그리디로 풀어보았다.

개념 공부 좀 해야겠다ㅎ