[SW 정글 20일차] 반례가 존재하는 것 같았는데..! 없었다 (백준1931 파이썬)

백준 1931 문제를 풀다가 85%에서 '틀렸습니다'가 나왔고, 틀리게 만든 케이스에 대해서 고민을 하였다. 몇 가지 반례를 찾을 수 있었다. 이를 해결한 코드를 제출하여 '맞았습니다'가 나왔다. 제출 이후 문득 생각난 케이스가 있어 '맞았습니다'가 나온 코드에 넣어서 테스트해 보았다. 예상 결과와 다른 값을 출력했다. 백준에서 검증하지 않은 케이스인 줄 알았지만, 글을 쓰면서 내가 생각을 잘못했다는 것을 깨달았다... 💩

그래도 잠깐이나마 백준 사이트의 '데이터를 추가한 사람' 리스트에 이름을 올릴 수 있나 행복회로를 돌렸기에 기록해두고자 한다.

 

백준 1931 문제 요약

입력되는 N개의 회의 시작, 끝 시각을 바탕으로 가장 많은 회의를 진행할 수 있는 경우의 수를 출력하는 것이다. 물론 회의실이 1개이기에 문제가 되고, 동시에 회의를 진행하거나 중간에 끊기는 경우는 없다.

문제 접근

처음에는 회의 시작 시각이 중요하다고 생각하였으나, 시작 시각으로 접근할 경우 '끝 시각 - 시작 시각'이 고려되지 않기에 테스트 케이스에도 적용이 되지 않았다. 이후 회의 시간을 고려하고자 하였으나 시작, 끝 시각이 겹쳐지는 경우가 있어 해결되지 않았다. 마지막으로 회의가 끝나는 시각을 기준으로 접근하였다.

회의가 끝나는 시각이 빠른 순으로 정렬하여 앞에서부터(=빨리 끝나는 회의부터) 회의를 선택하면 된다. 이때, 선택되었던 회의가 끝나는 시각보다 다음  회의의 시작 시각이 더 빨라야 한다. 만약, 끝나는 시각이 같은 회의가 있을 때는 시작 시각이 더 빠른 회의가 먼저 선택되도록 정렬이 필요하다.

반례(인 줄 알았지만 아니었던 것)

시작 시각	끝 시각	입력
1	2	5 1 2 2 4 3 4 3 4 5 5 5 5
2	4
3	4
3	4
5	5
5	5

위 케이스의 '최대 사용할 수 있는 회의'의 최대  개수는 4이다. 1 → 2 / 2 → 4 / 5 → 5 / 5 → 5 순으로 회의를 선택하는 것이다. 나는 5 → 5 처럼 시작과 끝이 같은 시각인 케이스를 존재하는 개수 만큼 반영해야 한다는 점을 고려하면서, 3 → 4 가 중복되는 것도 두 개로 카운트하기 위해 2 → 4 대신 3 → 4를 선택해야 하는 것이 아닌가 생각했다.

문제에서 동시에 회의를 진행할 수 없다는 조건도 있고, 처음, 끝 시각이 같은 케이스는 동시에 순차적으로 가능하다는 점에서 3 → 4 케이스와는 다르다.

 

이렇게 문제를 오해하여 반례를 생각했던 적은 처음이었다.

 

'데이터를 추가한 사람'에 이름 넣기는 허무하게 끝이났다 ^^.... 그래도 즐거웠다...

코드

n = int(input())

time_table = []
for i in range(n):
    st, en = map(int, input().split())
    # 시작, 지속시간, 끝[ [1, 3, 4], [3, 2, 5], ... , [12, 2, 14] ]
    time_table.append([st, en])

time_table.sort(key=lambda x :(x[1],x[0])) #끝나는 시간, 시작 시간 기준으로 오름차순 정렬

cnt = 0
last_endtime = 0

for i in range(len(time_table)):
    if last_endtime <= time_table[i][0]: # 지난 회의 끝 시점 <= 지금 회의 시작 시점
        last_endtime = time_table[i][1]
        cnt += 1 # 횟수 추가
        print(f"{cnt}번 째 회의의 시작 시각: {time_table[i][0]} 끝 시각: {time_table[i][1]}")
print(cnt)

 

---

해야할 것(하고 싶은 것)은 많은데,

시간이 너무 빨리 간다.

누가 시간 좀 멈춰줬으면 좋겠다.