백준 2098번, 외판원 순회 풀이

문제 백준 2098번 풀이 DP 점화식을 $dp[i][j] = i\ 정점에\ 방문했을\ 때\ j\ 정점들에\ 방문한\ 경우의\ 최솟값$ 이라고 두겠습니다. $j$만큼 방문했다는 것은 어떤 정점들에 방문했는지에 대해서 기록해둔다는 의미입니다. 이 $j$를 비트마스킹을 사용하여 처리할 것입니다. 일반적인 vector 등을 사용하여 처리할 수도 있지만, vector를 매번 재귀 함수의 매개변수로 넘겨주기에는 cost가 작지 않기 때문입니다. $j$를 이진수 정수로 두고 숫자 읽듯이 오른쪽부터 왼쪽 순서대로 읽을 겁니다. 그러면, 0번째 자리는 0번 정점에 방문했는지, 1번째 자리는 1번 정점에 방문했는지.. $k$번째 자리는 $k$번 정점에 방문했는지에 대한 정보를 담을 수 있습니다. 예..

2020.10.08