사업 확장 (COI 2012)

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

딱 봐도 NP-hard같은 문제를 N = 100을 주고 출제한걸 보니 당황하지 않을 수가 없었다. 일단 유일하게 생각해 볼수 있을 만한 접근법은 http://koistudy.net/?mid=prob_page&NO=369 와 같은 류의 바이토닉 기반 DP인거 같다. 한번 그 점을 생각해보고 어떠한 식으로 DP를 짜야지 최적 경로를 고려하는 점화관계를 이끌어낼 수 있는지 알아보자.

일단 생각을 쉽게 하기 위해서 1 -> 2로 가는 임의의 경로를 고정시키고, 그 경로상에서 2 -> 1로 오는 경로를 그려놓았다.

#1 같은 경우에는 그냥 플로이드 한번에 풀릴 거고

#2 같은 경우에는 위 링크건 문제를 풀어봤다면 그렇게 어렵지 않다. 다음과 같이 dp를 정의하자.

 * dp[i, j] -> [i -> 2]로 가는 경로 + [2 -> j] 로 가는 경로에서 사용한 정점의 수.

dp[2, 2]는 1이고, dp[1, 1]은 답이다. 저 점화식의 substructure는 다음과 같다.

 * dp[i, j] = dp[k, j] + dist(i, k) - (i == j)

 * dp[i, j] = dp[i, k] + dist(k, j) - (i == j)

 * for all k.

#3 같은 경우가 상당히 푸는 사람을 당황스럽게 하는데, 일단 저런 식으로 정방향으로 갔던 길을 타고 가는 경우에서

이런 식으로 돌아가는 방향의 길이 1) 겹치거나 2) 순서가 뒤바뀐 형태로 존재하지 않는다는 걸 증명해야 한다. 보다시피 저러한 형태의 경로는 꽤나 비효율적이라 그렇지 않음은 쉽게 보일 수 있다.

그렇게 생각하면, 현재 위치에서 아무 생각 없이 방향을 바꿔주기만 하더라도, 최적해와 같은 경우를 항상 표현할 수 있다는 것을 뜻한다. 고로.

 *  dp[i, j] = dp[j, i] + dist(i, j) - 1

에서 또 하나 갱신받으면 된다.

이 렇게 N^2개의 상태공간에 대한 N^3개의 관계식을 만들었으며, 상태끼리의 사이클이 있기 때문에 dijkstra's algorithm을 사용해서 문제를 해결해야 한다. 제대로 분석하기 쉽지 않은 문제임에도 불구하고 코드는 짧다. 시간 복잡도는 N^3lgN.