2098번 - 외판원 순회
dp[마을][상태] 로 했을 때는 맞고,
dp[상태]로 했을 때는 틀리네요.
외판원 순환문제 말고 007 문제나 발전소 문제는 1차원 dp로 풀리는데
이 문제는 왜 마을을 차원에 포함시킨 2차원 dp로 풀어야 하는지 이해가 잘 안되네요.
고수님들 초심자에게 설명 좀 부탁드리겠습니다 ㅠㅠ
현재 어떤 마을에 있는지에 따라서 값이 달라지기 떄문입니다
발전소 문제는 현재 어떤 위치에 있는지는 전혀 중요하지 않죠 !
1 -> 2 -> 3 -> 4 -> 5 인 경우와
1 -> 3 -> 2 -> 4 -> 5 인 경우가 있으면 dp[상태] 로만 체크하게 되면 1 -> 2 -> 3 과 1 -> 3 -> 2 를 같은 경우로 볼텐데요
3에서 4로 가는 것과 2에서 4로 가는 것은 다른 값을 가지기 때문에 현재 위치도 포함시켜주어야 합니다
댓글을 작성하려면 로그인해야 합니다.
marco2520332 6년 전 1
dp[마을][상태] 로 했을 때는 맞고,
dp[상태]로 했을 때는 틀리네요.
외판원 순환문제 말고 007 문제나 발전소 문제는 1차원 dp로 풀리는데
이 문제는 왜 마을을 차원에 포함시킨 2차원 dp로 풀어야 하는지 이해가 잘 안되네요.
고수님들 초심자에게 설명 좀 부탁드리겠습니다 ㅠㅠ