문제

• 
• 시간 제한: 1초
• 메모리 제한: 128MB

Problem Analysis

Naive하게 풀면, 경찰 a, b에 순차적으로 사건을 맡겨보면서 recursive 하게 풀 수 있다. 이때, 시간 복잡도는 O(2^N)이다. 그러나, sup-problem이 반복적으로 나타나기 때문에, Dynamic Programming으로 개선할 수 있다.

Algorithm

dp[a][b]에 경찰차 A, B 가 사건 a, b를 맡고 있을 때 가능한 최소 값을 저장한다.

1. Top-Down 방식으로 recursive하게 dp를 계산한다. (최소값은 dp[0][0]에 저장)

solve( a, b ):

dp[a][b] = min( 경찰차 1을 w로 움직이는 비용 + solve( w, b ), 
					경찰차 2를 w로 움직이는 비용 + solve( a, w) )

2. dp를 이용하여 최소가 되는 경로를 순회한다.

Data Structure

dp[w+1][w+1]

결과

Other

시간 복잡도는 O(N^2) 이다.
Bottom-Up 방식으로도 풀 수 있을 것 같지만, dp를 계산하고, 경로를 추적하는 함수가 더 복잡할 것 같다.