syndrome5044   2년 전

위상 정렬을 이용해서 AC를 받았습니다.

다만 그 과정에 이해가 잘 안가는 부분이 있는데,

첨부한 '오답 코드'에서는 전입차수가 0이 되는 건물들을 '건설 완료 시점을 key로 갖는 우선순위 큐'에 넣음으로써 건물의 건설 시각을 갱신해줄 때(특정 건물의 최종 건설 시각을 정할 때), 전입차수가 0이 되는 순간이 가장 늦은 시각이 되도록 하였습니다. (선행 건물이 2개 이상이라면 모두 완성되어야 해당 건물을 건설할 수 있게 되는데, 우선순위 큐를 이용함으로써 '늦게 끝나는 건물의 완성시간' + '해당 건물의 건설시간' 을 '해당 건물의 완성시간' 으로 정함)

해당 코드로 제출시 100% 시점에서 오답 처리가 되어 특정한 엣지케이스에서 통과하지 못하는 것으로 판단하고 해당 반례를 찾기 위해 여러 시도를 했지만 실패했습니다.

가장 의심가는 부분인 위 언급 부분을 우선순위 큐를 활용하지 않고 항상 선행 건물의 건설이 완료될 때마다 건설시간을 현재의 건설시간과 비교하고 업데이트해주는 식으로 변경하니 AC를 받았습니다.

질문

1. 두 코드의 동작이 동일하다고 보장된다 생각했는데, 그렇지 않은 이유가 있을까요?

2. 반례도 첨부해주시면 감사하겠습니다.

감사합니다.

sjyfantasy   2년 전

input : 1

1
7 6
8 1 1 1 1 1 1
1 5
2 5
3 6
4 6
5 7
6 7
7

output : 1

answer : 10

댓글을 작성하려면 로그인해야 합니다.