백준 1931-회의실 배정 (파이썬)

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

1931번: 회의실 배정

문제

한 개의 회의실이 있는데 이를 사용하고자 하는 N개의 회의에 대하여 회의실 사용표를 만들려고 한다. 각 회의 I에 대해 시작시간과 끝나는 시간이 주어져 있고, 각 회의가 겹치지 않게 하면서 회의실을 사용할 수 있는 회의의 최대 개수를 찾아보자. 단, 회의는 한번 시작하면 중간에 중단될 수 없으며 한 회의가 끝나는 것과 동시에 다음 회의가 시작될 수 있다. 회의의 시작시간과 끝나는 시간이 같을 수도 있다. 이 경우에는 시작하자마자 끝나는 것으로 생각하면 된다.

입력

첫째 줄에 회의의 수 N(1 ≤ N ≤ 100,000)이 주어진다. 둘째 줄부터 N+1 줄까지 각 회의의 정보가 주어지는데 이것은 공백을 사이에 두고 회의의 시작시간과 끝나는 시간이 주어진다. 시작 시간과 끝나는 시간은 231-1보다 작거나 같은 자연수 또는 0이다.

출력

첫째 줄에 최대 사용할 수 있는 회의의 최대 개수를 출력한다.

예제 입력 1

11
1 4
3 5
0 6
5 7
3 8
5 9
6 10
8 11
8 12
2 13
12 14

예제 출력 1

4

힌트

(1,4), (5,7), (8,11), (12,14) 를 이용할 수 있다.

 

---

시나리오

그리디란? 문제를 풀어나가는 과정, 단계에 있어서 가장 좋은 게 무엇인지 골라서 선택하는 풀이법

보통의 그리디 문제는 정렬과 동반된다. 따라서 정렬 후에 차례차례 가장 좋은 방법을 선택해 나가면 된다.

 

그렇다면 이 문제에서는 무엇을 기준으로 해서 가장 좋은 방법을 차례차례 선택해야 될까?

회의가 끝나는 시간을 기준으로 정렬하면 된다.

 

빨리 끝날 수록 남은 시간에 더 많은 회의를 진행할 가능성이 높아지기 때문이다.

오히려 시작하는 시간으로 정렬하게 되면 일찍 시작한 회의가 늦게 끝났을 때는 정답이 될 수없다.

 

 

정답 코드

import sys

input = sys.stdin.readline
n = int(input())
room = [list(map(int, input().split())) for _ in range(n)]
room.sort(key=lambda x: (x[1], x[0]))

cnt = 0
et = 0
for s, e in room:
    if s >= et:
        et = e
        cnt += 1

print(cnt)

 

피드백

이번 풀이에서도 확실하게 느낀건 풀이법을 선택해서 진행할 때 점점 복잡해지고 산으로 간다 싶으면 틀리게 풀고 있다는 것이다. 

빠르게 처음부터 다시 시작하는게 좋다.

이 문제는 큰 틀의 로직은 맞아도 사소한 실수 때문에 오답처리가 될 수 있는데 그 이유는 문제의 조건 속에 있다.

회의의 시작시간과 끝나는 시간이 같을 수도 있다. 이 경우에는 시작하자마자 끝나는 것으로 생각하면 된다. 라는 조건은

예를 들어 입력이

2

2 2

1 2

일 때, 두 회의시간 다 끝나는 시간이 2이기 때문에, 순서에 따라 2-2타임의 예약자들이 먼저 사용하게 되면 종료시간 보다 다음 타임의 시작 시간이 더 작기 때문에 카운팅 되지 않고 다음 차례로 넘어간다.

하지만 문제에서는 가능한 많은 회의 횟수를 요구하고 있으며 이 경우에는 정렬을 통해 둘다 카운트 될 수 있기 때문에 

리스트 room을 정렬 할 때 첫번째 기준을 끝나는 시간의 오름차순, 두번째 기준을 시작 시간의 오름차순으로 설정해줘야 한다.