https://www.acmicpc.net/problem/16991
문제요약
- 외판원 순회
- n = 16, 거리 = double
접근법
- python으로 구현해봄
- 0에서 시작해서 한바퀴 돔 (1, 2, ... 도 어짜피 한바퀴 돌면 같기때문에 해볼 필요 없음)
- dp[방문한곳들][마지막 방문]에서 다음 갈 곳을 전개
- "방문한곳들"에서 방문 안한 곳을 찾아서 : 새로운 곳
- dp[방문한곳들][마지막방문] + (마지막방문 -> 새로운곳 거리) = dp[새로운방문한곳들][새로운곳]
- dp[1][0] = 0으로 초기화, 나머지는 max값 : 0에서 시작할 것이므로
- dp[모든곳방문][마지막방문] + (마지막방문 -> 0번 거리) 들의 최소값
- 방문한 곳들은 bit로 표현 :
newbieski