qkrlwsnd   10일 전

질문 게시판에 있는 반례는 전부 통과하는 것 같은데 틀렸습니다가 뜨네요..

0~N 까지 N~0으로 초기화 하고

N+1부터 100000까지 위에서 구한 값을 통해서 최솟값을 구한 다음에

마지막으로 전체 구간(0~100000)을 한 번 더 점검해주는 로직입니다 ㅜ.ㅜ

djm03178   10일 전

이 문제와 같이 DAG가 아닌 그래프에서 특정 방향을 정해 놓고 dp를 하는 것은 매우 위험합니다. 그렇게 하는 것이 옳다는 증명을 할 수 없다면, 옳지 않을 가능성이 높습니다.

몇 가지 반례는 드리겠지만, 이와 같은 로직을 아예 포기하셨으면 좋겠습니다. 몇 가지 예외를 추가하거나 몇 차례 전체를 다시 dp를 돌리는 것으로 정답이 나올 수도 있지만, 왜 그렇게 하면 되는지에 대한 증명을 하는 것이 중요한 것이므로 단순히 정답이 나왔다고 해서 이와 같은 로직을 보다 일반적인 형태의 그래프에도 쓸 수 있을 것으로 생각하지 않으셨으면 좋겠습니다.

qkrlwsnd   9일 전

아..그렇군요

감사합니다!

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