이 문제는 각 도로를 기준으로 1번 지방역 방면의 지방역들은 상소문을 1번 지방역으로 보내고, N 번 지방역 방면의 지방역들은 상소문을 N번 지방역으로 보내도록 한 후 최소 비용 을 구하여 해결 할 수 있다. 즉, 한양역과 1번 지방역 사이의 도로, 1번 지방역과 2번 지방 역 사이의 도로, …, N - 1번 지방역과 N 번 지방역 사이의 도로, N번 지방역과 한양역 사이의 도로, 총 N + 1 개의 도로를 각각 없애보면서 일렬로 만든 뒤 그 중 최소 비용을 선택 한다.
일렬로 가정한 문제를 푸는 방법 중 가장 쉬운 방법은 모든 경우를 고려하는 것이다. 상소문을 가지고 있는 지방역에서 파발마를 바로 보낼 것인지 혹은 다른 지방역에서 오는 상소문을 기다린 후 함께 보낼지 여부를 결정하는 경우의 수는 2^N 가지다. 각각의 경우에 대해 비용을 계산하여 최소 비용을 선택하면 일렬인 상태에서 최소 비용을 구할 수 있으며, 이를 N개의 일렬에 모두 적용해 답을 구한다. 이 방법은 O( 2^N * N)의 시간 복잡도를 가지며 부분문제 1을 해결하여 11점을 받을 수 있다.
동적계획법(Dynamic Programming)을 활용하여 위의 방법을 개선할 수 있다. s번 지방역과 s+1 번 지방역 사이의 도로를 없앤 일렬의 경우를 처리 중이라고 가정한다. 만약, s = N 이라면, N 번 지방역과 한양역 사이의 도로를 없앤 경우이다.
A[i] 를 i번 지방역이 가지고 있는 상소문의 개수(0 혹은 1), S[i]를 1번부터 i번까지의 지방 역들이 가지고 있는 상소문의 개수라고 하자.
즉, 
이다.
D[i] 를 1번부터 i번까지 지방역이 한양에 모든 상소문을 보낼 때 최소 비용 (i <= s ) 으로, E[i] 를 i번부터 N 번까지 지방역이 한양에 모든 상소문을 보낼 때 최소 비용 (i > s) 으로 정의하자. 그러면 s번 지방역과 s+1 번 지방역 사이의 도로를 없앤 경우의 최소 비용은 D[s] + E[s+1]이 된다. 각각에 대한 점화식은 아래와 같다.
if A[i] = 1 , D[i] = min( D[j] + (S[i] - S[j] + 1) * i ) for 0 <= j < i else D[i] = D[i-1] if A[i] = 1 , E[i] = min( E[j] + ( S[j-1] - S[i-1] + 1) * ( N - i + 1) for i < j <= N + 1 else E[i] = E[i+1] 초기 값은 D[0]=0 , E[N+1] = 0 이다.
위의 방법으로 D와 E를 계산하는 시간복잡도는 O(N^2)이다. 이를 각 도로를 없애는 경우에 대해 반복하면 O(N^3)이 소요되며 부분문제 2를 해결하여 37점을 받을 수 있다.
위 방법에서 D ,E 의 값은 어떤 도로를 없애는지와 상관없이 항상 같은 것을 있다. 따라서 각 도로를 없앨 때 마다 동적계획법을 통해 계산하는 것이 아니라, 처음 한 번만 계산한 후 min( D[s] + E[s+1]) for 0 <= s <= N 을 구하여 시간복잡도 O(N^2)에 해결할 수 있다. 이 방법으로는 부분문제 3을 해결하여 58점을 받을 수 있다.
위의 방법을 더 개선하면 동적계획법을 O(N)에 해결할 수 있다. D 와 E는 방향이 반대일 뿐 같은 방법으로 구할 수 있기 때문에 아래에서는 D 의 값을 O(N)에 계산하는 방법만을 설명한다.
위의 점화식에서 min 함수의 변수인 j와 상관없이 일정한 값인 (S[i] +1) × i 항을 min 밖으로 뺀 후 정리하면 아래와 같다.
if A[i] = 1 , D[i] = min( D[j] - S[j] * i) + (S[i] + 1) * i for 0 <= j < i else D[i] = D[i-1]D[i]를 구하기 위해서는 D[j] - S[j] * i 값이 최소가 되는 j를 찾아야 한다. 이는 y = D[j] - S[j] * x 인 직선을 그래프로 그린 후 x=i 에서의 직선들 중 최솟값을 찾는 과정으로 생각할 수 있다. 이 문제에서 y = D[j] = S[j] * x 의 기울기 -S[j]는 j가 증가함에 따 라 항상 감소하기 때문에 어떤 i에서 j를 최적해로 참조하였다면 이후의 i의 최적해는 절대 j 이전의 값을 참조하지 않는다. 이를 이용하면 D[i] 를 순차적으로 구할 때 참조하는 x=i 에서 최솟값을 가지는 직선 j도 순차적으로 증가함을 알 수 있다.
각 i에 대해 D[i]가 계산된 후 직선 y = D[i] - S[i] × x 가 기존에 추가된 모든 직선보다 작아지는 지점이 있다면 이후에 D[i]를 계산할 때 이 직선이 참조될 가능성이 있기 때문에 이를 추가한다. 만약 그렇지 않다면 D[i]는 추후의 모든 x에 대해 답에 관여하지 못하므로 추가하지 않는다. 직선 y = D[i] - S[i] * x을 추가할 때 이 직선에 의해 추후에 답으로 참조 될 수 없는 기존의 직선들을 나중에 추가된 직선부터 차례로 제거한다.
결국 그려지는 직선들은 j가 커질수록 D[j]는 증가하고 -S[j]는 감소하며 가장 작은 j값이 x=i 에서 최솟값을 가지게 된다. 만약 가장 작은 j값이 x=i에서 더 이상 최솟값이 아니라면 직선 y = D[j] - S[j] * x를 그래프에서 제거한다.
추가된 직선들을 제거하는 과정과 새로운 직선을 추가하는 과정은 총 O(N)에 이루어지며, D[i]는 이 직선들을 이용해 총 O(N)에 구할 수 있다.