[백준] 1931번 회의실 배정(python)

https://www.acmicpc.net/problem/1931

1931번: 회의실 배정

 

나의 7전 8기 정신 😥 반례찾기 참 ㅇㅓ렵지만

 

해결했음에 감사하다~ 

 

 

1. 내가 작성한 코드

t = int(input()) #회의의 수
arr = [] #회의의 정보가 담긴 list
for i in range(t):
  time = list(map(int, input().split()))
  arr.append(time)

arr = sorted(arr, key = lambda x : (x[1],x[0]))
#끝나는 시간 순으로 정렬, 끝나는 시간이 같을 경우 시작 시간 순으로 정렬

cnt = 0
top = [0,0]

for i in arr:
  if i[0] >= top[1]: #전 회의의 끝 시간보다 시작시간이 크거나 같을 경우 회의 가능
    top = i
    cnt+=1

print(cnt)

 

1) 끝나는 시간 순으로만 정렬 2) 첫 top변수에는 arr[0]값을 주고, cnt=1로 시작했더니 17퍼 쯤에서 실패했다.

 

1)은 내가 발견해서 고쳤으나 2)는 끝끝내 찾지 못해서 질문게시판에 나와 같은 문제를 겪는 분을 보고 해결

 

 

1) 고친 이유

• [4,4] [1,4] 순서로 삽입될 경우, [4,4]회의가 배정되기 때문에 최적의 해가 아니다.

 

2) 고친 이유

• 회의의 개수가 1이고, 시작과 끝나는 시간이 같을 경우 cnt 가 중복으로 카운팅되어 오류가 발생한다.

 

 

2. 메모

• 반례가 항상 있을 수 있음을 의심하기
• 경계값을 기준으로 테스트 해보기