[platinum4] [해설,분류 미확인]9520 NP-hard

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

 

 

 

경계조건이 기발한 dp 문제.

우선위의 조건을 만족하려면 어떤 순서대로 방문해야 하는지 알아보자.

N = 10 이라고 한다면, 

우선 10번 도시는 반드시 맨앞이나 맨뒤에 와야 한다. 중간에 오면 작은 수의 도시들이 앞, 뒤에 모두 배치되기 때문이다.

 

 

 

그럼 10 은 맨앞, or 맨 뒤에 배치했다. 9또한 마찬가지로 10을 제외한 칸 중에 맨 앞, 맨뒤에 올 수 있을 것이다.

 

 

이런식으로 바깥 부터 하나씩 채워갈 수 있다. 

이렇게 바깥부터 채워나가야 한다면, dp 를 떠올리는건 어렵지 않다.

이런 식으로 채워져 있는 경우는 dp[4][5] =  지금까지 방문하는데 걸린 시간 최솟값 으로 두면 된다.

방문순서가 뒤바뀌어도 값은 같으므로, 이 경우도 마찬가지로 dp[4][5]이다.

 

여기서 잠깐 고민했던게, 그럼 dp[n][n] 을 n번 돌아야 하므로 O(N^3)인가 하는 생각이 잠깐 들었지만 아니였다.

10, 9,8,... i 를 돌았을 때 i번째의 경계값은 반드시,  i를 포함한다. 즉, dp[i][i + 1, i + 2... N] 이 경계값으로 만들 수 있는 것이다.

 

 

N = 10 일때 

처음값은 dp[10][0]

i = 9: dp[9][0] , dp[9][10]

i = 8 : dp[8][0], dp[8][9], dp[8][10] 

...

이렇게 나올 수 있다. 이때 0은, 아무와도 아직 연결되지 않았다는 뜻이다. dp[7][0] 은  10,9,8,7   or  7,8,9,10 이렇게 배치된 상태.

 

 

위 같이 dp[i][j] 인 상황에서 dp[i - 1][j] = dp[i][j] + C[i][i - 1] (C는 경로를 지날 때 드는 시간)

 또는  dp[i][i - 1] = dp[i][j] + C[i - 1][j] 로  만들 수  있다.

 

이제 최종적으로 1까지 연결한다면, dp[1][0] (1,2,3,4...10 or 10,9,8 ... 1 순서로 연결)  or dp[1][2], dp[1][3], dp[1][4] ... dp[1][10] 까지 나올 것이다.  그런데 아직 1과 2,3,4..10은 아직 연결되지 않았으므로, 

dp[1][i] += C[1][i] 로 마무리 하면 된다. (i = 2,3,4...10)