Greedy Algorithm (1) - 백준 1931 : 회의실 배정

그리디 알고리즘 (탐욕법) 을 적용할 수 있는 방법은 여러가지가 존재한다.

그리디 알고리즘은 단순히 설명하자면, 완전탐색이나 동적 프로그래밍처럼 가능한 모든 해를 둘러보지않고, 부분적으로 지금 당장 좋은 방법만을 선택해가는 방법이다.

 

www.acmicpc.net/problem/1931 회의실 배정 문제를 풀어보며 익혀보자.

 

회의실 배정 문제에 그리디 알고리즘을 적용하여 푼다고 생각했을 때 (다른방식으로도 풀 수 있다.)

• 단순히 첫번째회의(회의시간 오름차순 정렬) 를 선택하고, 겹치는 것들을 제거한 후에 다시 가장 먼저 나오는 회의를 선택할 수도 있다.
• 다른 방식으로, 회의 길이가 짧은 순서대로 선택해 나갈수도 있다.

이처럼 문제를 푸는 방식은 여러가지가 존재한다. (물론 다 옳은 답을 내는것은 아니다. 접근방법이 여러가지라는 것일 뿐)

위 두 방식은 이 문제에 적용할 때 쉽게 반례를 찾을 수 있다.

첫번째 방식은 예를들어 가장 일찍 시작한 회의가, 너무 오래걸리는 경우이다. 아침에 회사가자마자 회의를 시작했는데 저녁까지 한다면...

두번째 방식은 긴 2개의 회의 사이에 짧은 회의가 1개 걸쳐있는 경우이다. 적절한 답은 2가 되야겠지만 짧은 회의 1개를 답으로 내놓는다.

 

이 문제에서 중요한것은 회의의 시작시간과, 끝나는시간중에서 '끝나는 시간'이다.

 

이 문제를 풀며 우리가 해야하는것은 '끝나는 시간'을 기준으로 오름차순으로 정렬한 후에 가장 먼저 끝나는 회의들의 집합을 구하는 것이다.

 

import sys
input = sys.stdin.readline

n = int(input())
arr = []
for _ in range(n):
	# 회의 시간들을 입력받는다.
    start, end = map(int,input().split())
    arr.append([start,end])

# 끝나는시간, 시작시간에대해 오름차순으로 정렬한다.
arr = sorted(arr, key = lambda x:(x[1], x[0]))

earliest = 0 # 회의를 시작할 수 있는 시간
result = 0
for i in arr:
    begin, end = i[0], i[1]
    if  earliest <= begin:
        # 회의가 끝나는 시간부터 다시 시작할 수 있다
        earliest = end
        result +=1

print(result)

회의실 시간들을 입력받은 배열 arr 을 정렬할 때 주의해야 할 것은

 

arr = sorted(arr, key = lambda x : (x[0], x[1]) 로 정렬할 경우 문제를 틀리게 되는것인데

왜냐하면 이것은 시작시간을 기준으로 선 정렬한 후에 끝나는 시간으로 정렬하게 되면서, 우리가 원하는 가장 먼저 끝나는 회의를 선택하는것이 되지 않기 때문이다.

 

또한 

 

arr = sorted(arr, key = lambda x : x[1]) 과 같이 끝나는 시간만 고려하여 정렬한 경우에도 문제를 틀리게 되는데

왜냐하면, 회의 시간들중에는 5시에 시작해서 5시에 끝나는 데이터도 포함되어 있기 때문이다.

 

예를들어

 

3시에 끝나는 회의 후에 (5,5) 와 (4,5) 가 있다고 하자.

시작시간에대한 정렬은 되지 않아 (5,5) 만 계산한다면 (4,5)는 포함되지 않지만

(4,5)를 먼저 계산하면 (5,5)도 계산 가능하다. 따라서 (끝나는시간,시작시간)으로 정렬해 주어야 한다.