13549번 - 숨바꼭질 3
queue.appendleft(2*a)를 하지 않고 queue.append(2*a)로 deque에 오른쪽에 append할 경우 틀리는 이유가 궁금합니다.
시간 복잡도는 전자가 더 빠르다는 것은 이해하였으나, dp[2*a]>dp[a]라는 조건문이 항상 최솟값을 보장한다고 생각했는데 뭐를 잘못 생각한걸까요
웬만한 반례는 전부 통과했고 오랜 고민 끝에도 답이 나오지 않아 질문 드립니다.
http://boj.kr/2a7bfafd326444a4...작성자님이 올려주신 코드에서 제가 appendleft를 append로 고쳐서 제출해 보았는데 틀리지 않습니다.
참고로 이 문제에서 2a를 오른쪽에 append 해도 시간 초과가 나지 않는 것은 이 문제 상황의 특수성 때문입니다. 일반적인 가중치 0,1로 이루어진 그래프에서는 가중치 0 간선을 오른쪽에 append 할 경우 시간복잡도가 지수 시간으로 증가하게 해서 터뜨리는 것이 가능합니다.
댓글을 작성하려면 로그인해야 합니다.
shoot0428 1년 전
queue.appendleft(2*a)를 하지 않고 queue.append(2*a)로 deque에 오른쪽에 append할 경우 틀리는 이유가 궁금합니다.
시간 복잡도는 전자가 더 빠르다는 것은 이해하였으나, dp[2*a]>dp[a]라는 조건문이 항상 최솟값을 보장한다고 생각했는데 뭐를 잘못 생각한걸까요
웬만한 반례는 전부 통과했고 오랜 고민 끝에도 답이 나오지 않아 질문 드립니다.