BOJ 12932 노래방

노래방
(http://boj.kr/12932)

한 2주 동안 고민해서 풀었는데, 사실 간단한 방법이라서 허무했다.
영선이와 효빈이가 각자 뭘 고를지를 정할 필요 없이, 마지막에 골라진 두 수만 알고 있으면 된다.
\(D[i][j]\)를 \(i\)번째 수와 \(j\)번째 수가 마지막 수일 때 최소 난이도라고 정한다.
그러면 경우는 3가지가 있다.
영선이가 쭉 골라오다가 효빈이가 지금 처음 고르는 것이라면 \(D[i][i-1]\)는 현재까지의 난이도 총합이 된다.
그리고 \(i-1\)번째 수와 \(j\)번째 수가 마지막인 경우, \(D[i-1][j]\)에서
\(i-1\)번째 수에서 \(i\)번째 수로 넘어온다면 \(D[i][j]\)를 갱신할 수 있고,
\(j\)번째 수에서 \(i\)번째 수로 넘어온다면 \(D[i][i-1]\)를 갱신할 수 있다.

#include <bits/stdc++.h>
 
using namespace std;
 
int arr[2000], d[2000][2000];
 
int main() {
  int n;
  scanf("%d", &n);
 
  for (int i = 0;i < n;++i)
    for (int j = 0;j < n;++j)
      d[i][j] = 2e9;
  
  int tot = 0;
  for (int i = 0;i < n;++i) {
    scanf("%d", &arr[i]);
    if (i == 0)
      d[0][0] = 0;
    else {
      d[i][i - 1] = tot;
      for (int j = 0;j < i;++j) {
        d[i][j] = min(d[i][j], d[i - 1][j] + abs(arr[i] - arr[i - 1]));
        d[i][i - 1] = min(d[i][i - 1], d[i - 1][j] + abs(arr[i] - arr[j]));
      }
      tot += abs(arr[i] - arr[i - 1]);
    }
  }
  
  int mn = 2e9;
  for (int i = 0;i < n;++i)
    mn = min(mn, d[n - 1][i]);
  
  printf("%d", mn);
 
  return 0;
}