BOJ 15747 - Taming the Herd

BOJ 15747 - Taming the Herd

$O(N^3)$ DP 로 풀 수 있다.

$dp[i][j]$ 를 $i$ 번 이전까지 $j$ 개의 그룹으로 묶었을 때 최솟값이라고 하면 각 테이블을 $O(N)$에 갱신해줄 수 있다.

void solve() {
   int n;
   cin >> n;
   vi a(n + 1);
   fv1(a);
   // i 번째 전까지 j 개의 그룹으로 묶었을 때 최솟값
   vvi dp(n + 2, vi(n + 2, 1e9));

   dp[1][0] = 0;
   for (int i = 1; i <= n; i++) {
      for (int j = 0; j <= i - 1; j++) {
         if (dp[i][j] == 1e9) continue;

         int cost = 0, nxt = 0;
         for (int k = i; k <= n; k++, nxt++) {
            if (a[k] != nxt) cost++;
            mina(dp[k + 1][j + 1], dp[i][j] + cost);
         }
      }
   }
   for (int i = 1; i <= n; i++) {
      cout << dp[n + 1][i] << endl;
   }
}