[BOJ / Python] 1931 회의실 배정

🧩 문제 : 1931번

💪🏻 해결 방법 

1️⃣ 그리디 알고리즘 이용 

1. 시작 시간, 종료 시간을 기준으로 회의 시간 정렬 

2. 회의 종료 시간과 같거나 큰 회의 시작 시간이 있다면 회의 종료 시간 갱신 + 회의 개수 증가 

 

첫번째 코드 - 틀렸습니다

import sys

# 입력
n = int(sys.stdin.readline())  # 회의의 수 N

for _ in range(n): # 회의 시간 입력
    start, end = map(int, input().split())
    time.append([start, end])

time = []  # 회의 시간
count = 1  # 회의의 개수

time.sort(key=lambda x: (x[1], x[0])) # 시작시간, 종료시간을 기준으로 회의 시간 정렬 

end_time = time[0][1] # 첫 회의 종료 시간 
for i in range(n):
    if end_time <= time[i][0]: # 회의 종료 시간과 같거나 큰 회의 시작 시간이 있다면
        end_time = time[i][1] # 회의 종료 시간 갱신 
        count += 1 # 최대 회의 개수 증가 

print(count)

왜요!!!!!!!!!!!!!!!!!!!!!!!

정답 코드 

import sys

# 입력
n = int(sys.stdin.readline())  # 회의의 수 N

for _ in range(n): # 회의 시간 입력
    start, end = map(int, input().split())
    time.append([start, end])

time = []  # 회의 시간
count = 1  # 회의의 개수

time.sort(key=lambda x: (x[1], x[0])) # 시작시간, 종료시간을 기준으로 회의 시간 정렬

end_time = time[0][1] # 첫 회의 종료 시간
for i in range(1, n):
    if end_time <= time[i][0]: # 회의 종료 시간과 같거나 큰 회의 시작 시간이 있다면
        end_time = time[i][1] # 회의 종료 시간 갱신
        count += 1 # 최대 회의 개수 증가

print(count)

인덱스 문제 였음!

count의 초기 값을 1로 설정해서 0번째 회의를 제외하고 for문을 돌려야하는데 0번째 인덱스도 비교해서 count가 하나 더 나왔던 것이었음 .. ㅇㅅㅇ

따라서 1번째 인덱스부터 비교하도록 for문의 range를 변경했더니 성공 ~.~

 

🎁 성공!