marco2520332   6년 전

dp[마을][상태] 로 했을 때는 맞고,

dp[상태]로 했을 때는 틀리네요.

외판원 순환문제 말고 007 문제나 발전소 문제는 1차원 dp로 풀리는데

이 문제는 왜 마을을 차원에 포함시킨 2차원 dp로 풀어야 하는지 이해가 잘 안되네요.

고수님들 초심자에게 설명 좀 부탁드리겠습니다 ㅠㅠ

rdd6584   6년 전

현재 어떤 마을에 있는지에 따라서 값이 달라지기 떄문입니다

rdd6584   6년 전

발전소 문제는 현재 어떤 위치에 있는지는 전혀 중요하지 않죠 !

chfhddl0127   1달 전

1 -> 2 -> 3 -> 4 -> 5 인 경우와

1 -> 3 -> 2 -> 4 -> 5 인 경우가 있으면 dp[상태] 로만 체크하게 되면 1 -> 2 -> 3 과 1 -> 3 -> 2 를 같은 경우로 볼텐데요

3에서 4로 가는 것과 2에서 4로 가는 것은 다른 값을 가지기 때문에 현재 위치도 포함시켜주어야 합니다

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