[Python] BOJ(백준) 1931번 - 회의실 배정

링크

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

난이도(solved.ac 참고)

실버2

풀이

이 문제를 풀면서 lambda를 처음 사용해봤다. 알고리즘 수업을 들으면서 회의실 배정 문제를 이론으로만 접했었는데, 당시에 끝나는 시간이 빠른 순서대로 하는 것이 최적의 결과를 가져온다는 것을 깨닫고 lambda 함수를 이용하여 끝나는 시간인 x[1]을 기준으로 나열했고, 2순위로는 시작 시간인 x[0]을 기준으로 나열했다.

 

여기서, 왜 2순위로 시작 시간을 뒀는가?

- 이부분은 예시로 들어서 설명해야 한다.

2
3 3
1 3

이런 예시가 있다고 하자. 이 경우에 2순위로 시작시간을 나열하지 않는다면 3 3이 먼저 실행이 되고, (3 3)의 뒷자리보다 (1 3)의 앞자리가 더 작기 때문에 (1 3)은 무시되어 카운트되지 않는다. 그래서, (1 3) (3 3) 순으로 나타내기 위해 2순위로 시작 시간을 둬야 한다.

 

그 이후 부분은 어렵지 않다.

끝나는 시간이 빠른 순서대로 나열이 되어 있으므로, 우선 첫 번째로 나열된 회의는 바로 진행이 될 것이다. 따라서 count를 기본 1로 설정했다.

여기서 우리가 비교해야 할 값은, now(첫 회의의 종료 시간)과 i번째 인덱스의 시작 시간이다. 후자가 더 크거나 같을 경우 종료하는 즉시 그 다음 회의가 시작되게 되므로 배정 횟수인 count의 값을 1 더해주고, now를 i번째 인덱스의 종료 시간으로 업데이트 해준다.

이렇게 될 경우 다음 for문을 돌면서는 그 바뀐 now와 i번째 인덱스의 시작 시간을 비교하게 된다.