BOJ 9520 : NP-Hard

https://www.acmicpc.net/problem/9520

이 문제를 풀기 전 KOI 2003 경찰차 문제를 풀고 오는 것을 추천한다.

 

우리는 이 문제를 좀 바꾸어 생각해보면, 1부터 N까지의 자연수를 순서대로 앞 또는 뒤에 수를 추가하는 방식으로 수열을 만들고, 이를 순서로 해서 모든 도시를 방문할 때 비용의 최솟값을 구하는 문제이다.

 

이는 dp로 해결할 수 있다.

dp[i][j] = 수열의 가장 왼쪽에 i가 있고, 가장 오른쪽에 j가 있을 때 최소 비용

 

dp[max(i,j)+1][j] = min(dp[max(i,j)+1][j], dp[i][j]+cost[i][max(i,j)+1])
dp[i][max(i,j)+1] = min(dp[i][max(i,j)+1], dp[i][j]+cost[j][max(i,j)+1])

 

경찰차 + 약간의 관찰이 들어간 문제이다. 괜찮다고 생각.

코드