[파이썬] 백준 1931 회의실 배정

# 백준 1931 회의실 배정

n = int(input())

# 회의 시작시간 끝나는 시간
arr = []
for i in range(n):
    arr.append(list(map(int, input().split())))

arr.sort()
s, e = arr[0][0], arr[0][1]

res = 1
for i in range(1, n):
    if arr[i][1] < e:
        s, e = arr[i][0], arr[i][1]
    else:
        if arr[i][0] >= e:
            res += 1
            s, e = arr[i][0], arr[i][1]
        
print(res)

알고리즘 분류

- 그리디 알고리즘

- 정렬

 

그리디 문제는 ex) '가장 큰 순서대로', '가장 작은 순서대로'와 같은 기준을 알게 모르게 제시해준다. (이코테 참조)

그리디 유형의 문제들은 현재 상황에서 특정한 기준에 따라 가장 좋아 보이는 것만을 선택해서 최적의 해를 구해야 한다.

 

문제풀이

1. 첫번째 튜플을 기준으로 둔다.

2. 다음 튜플을 비교한다. 만약 기준 튜플의 두번째 값보다 기준 다음 튜플의 두번째 값이 더 작다면 (여기서 두번째 값이라면 튜플 중에서 두번째 값) 기준 튜플을 다음 튜플로 바꾼다.

만약 더 크다면 튜플의 첫번째 값들을 비교해서 기준 튜플의 두번째 값보다 크면 추가를 하고 작으면 pass

 

** (튜플 첫번째 값, 튜플 두번째 값) **

 

이렇게 문제를 풀면 일단 틀린다. 그 이유는 튜플들을 정렬을 해주지 않았기 때문이다. 튜플을 정렬을 하지 않았다면 기준 튜플의 의미가 없어지기 때문이다. 그러므로 문제풀이 1번을 실행하기 전에 튜플들을 정렬해주어야 한다.