na982   6년 전

전형적인 위상정렬로 indegree count를 유지하면서 0이 될때 update 하는 형식으로 구현을 했는데,
최적 시간 update를 indegree 가 0 이 되는 시점에만 해도 될것같은데, 이렇게 하면 wrong answer 가 되네요;
곰곰히 생각해봐도 어떤케이스에서 wrong answer가 되는지 잘 모르겠네요;
고수님들 도와주세요~ㅎㅎ
미리 감사드립니다.

kdk8361   6년 전

3이라는 작업을 완료할 때 1,2라는 작업을 먼저 완료해야 한다고 합시다. 1 작업에는 100이 걸리고 2 작업에는 10이 걸린다고 했을 때 next : adj[cur] 가 1부터 가져올 경우 최종적으로 10이 update 되겠죠. indegree가 0이 되는 순간의 작업시간이 최대 시간이라고 보장 할 수가 없습니다.

3
100 0
10 0
5 2 1 2


na982   6년 전

감사합니다. 저도 님처럼 잘하고 싶네요~ㅎㅎㅎ

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