BOJ 1931 회의실

N = int(input())
time = [] # 배열 넣을 수 있는 리스트 만듦

for _ in range(N):
  start, end = map(int, input().split())
  time.append([start, end])

time = sorted(time, key=lambda a: a[0]) # 시작 시간을 기준으로 오름차순
time = sorted(time, key=lambda a: a[1]) # 끝나는 시간을 기준으로 다시 오름차순

last = 0 # 회의의 마지막 시간을 저장할 변수
conut = 0 # 회의 개수를 저장할 변수

for i, j in time:
  if i >= last: # 시작시간이 회의의 마지막 시간보다 크거나 같을경우
    conut += 1
    last = j

print(conut)

처음으로 그리디를 써서 푸는 문제를 풀어봤다.

그리디는 말 그대로 탐욕이라는 뜻으로, 문제를 풀기 위해 최대한 적은 비용을 들여 최소/최대 비용을 도출할 수 있도록 하는 형태이다.

그렇기에 배열 정렬같은 것들로 count를 구하는 것이 필요하고 구하는 방법은 다양하다.

 

나는 <시작시간이 회의 마지막 시간보다 크거나 같을 경우>같은 로직은 생각하였는데 시작시간과 회의시간이 같을 경우등을 고려하지 못하였고,

시작 시간 기준으로 오름차순으로 정렬한 뒤, 끝나는 시간 기준으로 다시 오름차순으로 정렬한다는 아이디어를 생각하지 못하였다.

그리고 각각의 묶음들을 list에 집어넣는 로직을 생각해보지 못하였다. 이는 sorted, list들의 개념이 부족해서라고 생각한다.

관련 개념을 익히고 같은 문제가 나왔을 때 이용하자.