알고리즘 (PS)/BOJ
[백준] 2098 - 외판원 순환 (G1)
https://www.acmicpc.net/problem/2098 2098번: 외판원 순회 첫째 줄에 도시의 수 N이 주어진다. (2 ≤ N ≤ 16) 다음 N개의 줄에는 비용 행렬이 주어진다. 각 행렬의 성분은 1,000,000 이하의 양의 정수이며, 갈 수 없는 경우는 0이 주어진다. W[i][j]는 도시 i에서 j www.acmicpc.net 간만에 만난 진짜 너무 이해하기 어려웠던 문제이다. 이 문제를 풀고 이해하는데 3시간이 걸렸다 (이래야 골드1이지..) 이 문제의 핵심은 3가지다. 1. 최적해는 결국 사이클이기 때문에 어디에서 시작점을 잡아도 좋다. 2. 지금까지의 누적된 값에 내 값을 더해주는게 아니라, 누적될 값을 넘긴다. 3. 최소를 구할 때도 0을 조심하자. 1. 최적해는 결국 사이클..
