[BOJ] 10272번: 현상금 사냥꾼

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

문제를 조금 변형해 가장 왼쪽의 점에서 2개의 경로를 출발시킨다고 생각해봅시다. 가장 왼쪽의 점과 가장 오른쪽의 점을 제외한 N-2개의 점에 대해서는 두 경로 중 하나만 도달하고, 가장 왼쪽의 점과 가장 오른쪽의 점은 두 경로 모두 도달합니다. 우리가 원하는 것은 두 경로의 길이의 합을 최소로 만드는 것입니다.

그리고 D[a][b]를 한 개의 경로는 점 a까지 도달했고, 다른 한 개의 경로는 점 b까지 도달했을 때 경로의 길이의 합의 최소라고 해봅시다. 그리고 편의상 a < b라고 둡시다.

이 때 D[i][i+1]은 min(D[k][i] + dist(k, i+1))으로 구할 수 있고, D[i][i+k] (k > 1)은 D{i][i+k-1]+dist(k-1,k)로 구할 수 있습니다.

정답은 min(D[i][N]+dist(i,N))입니다.

https://github.com/blisstoner/BOJ/blob/master/10272.cpp