BOJ 12932 - 노래방

BOJ 12932 - 노래방

$dp[i][p_1]=$ $i$ 번째 음을 볼 차례이고 더 이전에 불렀던 사람이 $p_1$ 번째 음을 불렀을 때 끝까지 부르는데 최소값

라고 두고, $p_1=0$ 일 때는 아직 안 부른 것으로 취급한다.

시간복잡도 $O(n^2)$ 로 구할 수 있다.

int n, a[2001], dp[2001][2001];  
  
// i 번째 음을 볼 차례이고 더 일찍 부른 사람이 마지막으로 p를 불렀을 때 끝까지 부르는데 최소값  
int fn(int i, int p1) {  
   if (i == n + 1) return 0;  
  
   int &ret = dp[i][p1];  
   if (~ret) return ret;  
   ret = 1e9;  
  
   assert(p1 == 0 || p1 < i - 1);  
   int a_cost = p1 == 0 ? 0 : abs(a[i] - a[p1]);  
   int p2 = i - 1;  
   int b_cost = p2 == 0 ? 0 : abs(a[i] - a[i - 1]);  
  
   // 더 이전에 부른 사람이 부르는 경우  
   ret = a_cost + fn(i + 1, p2);  
   // 더 후에 부른 사람이 부르는 경우  
   ret = min(ret, b_cost + fn(i + 1, p1));  
  
   return ret;  
}  
  
void solve() {  
   memset(dp, -1, sizeof dp);  
   cin >> n;  
   for (int i = 1; i <= n; i++) cin >> a[i];  
   cout << fn(1, 0);  
}