[백준] 1931 회의실 배정

iamjinseo·2022년 8월 8일

그리디 백준

문제풀이-Python

목록 보기

35/134

문제

입출력

시도

1

런타임 에러로 틀림
arr[i][0]>=arr[i-1][1]: 부분에서 틀림 근데 왜 아직도 오류인지 모르겠음
어차피 for i in (1,N)인데 괜찮은 거 아냐?

라고 생각했는데 방금 생각났는데 range가 없음ㅋㅋㅋㅋ

2

그냥 틀림

이유 : 회의가 끝나는 시간 기준 정렬한 시도는 좋았으나 회의 시간은 전혀 고려하지 않았음
예를 들어 회의가
(1 3)
(3 6)
(4 5)

3

결국 반례, 질문을 많이 보고 해결함!
일단 arr에 시작시간 끝시간 뿐만 아니라 회의 진행시간도 계산해서 삽입했다.
그리고 회의시간 기준으로 정렬한 다음 끝나는 시간으로 정렬했다.

다른 사람의 해설을 통째로 보지 않고 질문 게시판을 보면서 코드를 고쳐나가는 방식으로 스스로 해결했다ㅎㅎ 뿌듯

7
3 10
2 2
1 3
2 2
9 10
4 9
2 2
이런 반례를 봤는데, 3번째 시도에서 고친 것 처럼 회의시간으로 정렬->끝나는 시간으로 정렬하면

이런 결과가 나온다.
마지막 줄의 [9, 10, 1]과 [3, 10, 7]에 주목해보자. 회의시간으로 정렬 후 끝나는 시간으로 정렬하였더니 둘 다 끝나는 시간은 같지만 회의시간이 훨씬 긴 [3, 10, 7]이 자동으로 뒤쪽에 정렬되었다.

이처럼 두 차례의 정렬을 거치는 방식으로 회의시간이 더 긴 회의를 무조건 후위순위로 놓을 수 있는 셈이다.

그런데 [1, 3, 2]를 보면서, 만약에 저 회의가 [1, 2, 1]이면 타임라인에 껴줘야 하는데, 내가 쓴 조건식 if i[0] >= res[-1]: #시작시간이 결정된 회의시간의 끝나는시간과 같거나 커야함으로는 충족할 수 없었다.

따라서 새로운 조건문을 써 주었다.
elif i[0] <= res[-1][0] and i[1] <= res[-1][0]: #시작시간과 끝나는 시간이 타임라인 앞에 있는 경우
이렇게 하면 위와 같은 상황에서 [2, 2, 0]앞에 [1, 2, 1]회의를 넣을 수 있다ㅎ

코드

# 백준 1931 회의실 배정 그리디 실버1
import sys
input = sys.stdin.readline

N = int(input())
arr=[]
for i in range(N):
    a, b = list(map(int, input().split()))
    dur=b-a #회의시간
    arr.append([a, b, dur])

arr.sort(key=lambda x:x[-1]) # 이차원 배열에서 마지막 인덱스 기준 정렬
# print(arr)
arr.sort(key=lambda x:x[1])
# print(arr)
res =[]
for i in arr : 
    try:
        if i[0] >= res[-1][1] :
            # print(i)
            res.append(i)
        elif i[0] <= res[-1][0] and i[1] <= res[-1][0]:
            # print(i)
            res.append(i)
    except:
        res.append(i)
    # print("res:", res)
print(len(res))