백준 1931번 - 회의실 배정

회의실 배젇 문제 바로 가기

풀이 날짜: 2026-01-14

baekjoon 알고리즘 문제 풀이

풀이 코드


import sys
input = sys.stdin.readline

n = int(input())
times = []

for _ in range(n):
    start, end = map(int, input().split())
    times.append((start, end))
times.sort(key=lambda x: (x[1], x[0]))

count = 0
end_time = 0

for start, end in times:
    if start >= end_time:
        count+=1
        end_time = end

print(count)

문제 핵심 요약:

해결 전략을 세우며 가장 먼저 고민한 것은 “어떤 회의를 먼저 선택해야 이후 선택의 폭이 넓어질까”였다.

이 질문에 대한 답은 회의의 시작 시간이 아니라 끝나는 시간에 있었다. 빨리 끝나는 회의를 먼저 선택할수록 다음 회의를 배치할 수 있는 시간이 많아지고, 그 결과 더 많은 회의를 선택할 수 있다고 판단했다.

이 순간, 이 문제가 그리디 알고리즘이라는 확신이 들었다.

정렬 기준을 결정

끝나는 시간을 기준으로 정렬한다는 아이디어는 비교적 빠르게 떠올랐지만, 그 자체로는 충분하지 않다는 점을 구현 과정에서 깨달았다.

끝나는 시간이 같은 회의가 여러 개 존재할 수 있고, 이 경우 어떤 회의를 먼저 고려하느냐에 따라 이후 선택 가능 여부가 달라질 수 있었다.

그래서 정렬 기준을 다음과 같이 정리했다.

1차: 끝나는 시간
2차: 시작 시간

조건 확인

매 반복마다

현재 회의의 시작 시간이
마지막 회의의 종료 시간 이후인지

이 조건만 확인해 회의를 선택했다.

구현 과정에서 겪은 어려움

처음에는 “끝나는 시간만 정렬하면 충분하지 않을까?”라는 생각을 했지만, 반례를 통해 그 생각이 틀렸다는 것을 확인했다.