N = int(input())
graph = [[*map(int,input().split())] for _ in range(N)]
DP = [[1e9]*N for i in range(N)]
DP[0][0] = 0
for start in range(1,N):
for end in range(start):
DP[start][end] = min(DP[start][end],graph[start][start-1]+DP[start-1][end])
DP[start][start-1] = min(DP[start][start-1],graph[start][end]+DP[start-1][end])
print(min(DP[-1]))다이나믹 프로그래밍으로 해결하였다.
문제 해석도 까다롭고 풀이 아이디어도 쉽지 않은 문제였다.
일단 핵심은, 문제의 조건대로 움직이기 위해서는 "내림차순+오름차순" 의 순서대로 움직여야한다는 것이다. 예를 들어 N=7인 경우 '1234567' 또는 '7654321' 처럼 내림차순과 오름차순 둘 중 하나로만 이루어져 있거나, '7651234' 또는 '7531246' 처럼 내림차순과 오름차순이 순서대로 한번씩 나오는 경우는 문제의 조건을 만족한다. 그러나 '7651243' '1234765'와 같은 경우에는 성립하지 않는다.
방문 순서의 규칙을 알았다면 이를 최적화하여 구현해야한다. 풀이를 설명하면,
1. 2차원 DP를 만든다. DP[start][end]는 start에서 출발하여 end로 끝날 때, start 이하의 모든 지점을 방문하여 end에서 방문이 끝나는 경우의 최솟값을 의미한다.
2. start와 end의 차이가 1보다 큰 경우, DP[start][end]는 start에서 start-1로 이동한 후 start-1에서 end로 이동하는 것과 같다.
3. start와 end의 차이가 1인 경우(즉 end = start-1), DP[start-1][end]+graph[end][start] 값들의 최솟값이 DP[start][end]가 된다.
4. 2,3의 과정으로 bottom-up 하여 DP 배열을 채우고, DP[N] 중 최솟값을 출력한다.
문제를 다 풀고나서 알게된 사실인데, 이 문제가 사실 경찰차 [백준 2618번] 경찰차 (Python3) (tistory.com) 문제와 똑같은 방식으로 풀 수 있는 문제였다. 간선이 양방향이기 때문에 내림차순+오름차순 순서로 방문하는 것이 사실 1번 지점에서 두 경찰차가 N까지 겹치지 않고 가는 것과 똑같기 때문이다.
힘들게 푼 문제가 예전에 푼 문제와 사실 똑같은 문제였다니 허무하기도 했지만 어쨌든 그로 인해서 나는 경찰차, 또는 이 문제를 Top-down 방식과 Bottom-up 방식, 두 가지 방식으로 풀 수 있게 된 셈이기도 하니 긍정적으로 생각해야겠다.