[백준] 15747 - Taming the Herd (c++)

USACO 2018 February Contest > Gold 3번 문제이다.

https://www.acmicpc.net/problem/15747

 

문제 요약

N길이의 수열 a가 주어진다.

수열을 k개의 그룹으로 나눌 수 있는데 각 그룹은 0부터 1씩 증가하는 수열이 된다.

수열을 1~N개로 그룹으로 나눴을 때 a와 다른 원소 개수의 최솟값을 각각 구해라.

 

풀이  (N^3)

• DP

문제 이해만 했다면 DP 문제란 걸 쉽게 알 수 있다. 갱신하는 게 조금 어려웠는데 이렇게 할 수 있다.

일단 dp[i][j]를 i까지 j개의 그룹으로 나눴을 때 다른 원소 개수의 최솟값으로 정의하고 dp[i][j]에서 dp[i+1~n][j+1]의 최솟값을 갱신해 나가면 된다. 이렇게 하면 N^3의 시간복잡도로 dp테이블을 전부 채울 수 있다.

#include <bits/stdc++.h>
using namespace std;
#define ll long long

int main() {
    cin.tie(0)->sync_with_stdio(0);

    int n;cin>>n;
    int a[n+1];
    for(int i=1;i<=n;i++) cin>>a[i];

    vector<vector<int>> dp(n+1,vector<int>(n+1,1e9));
    dp[0][0] = 0;
    for (int i=0;i<n;i++) {
        for (int j=0;j<=i;j++) {
            for(int k=i+1,num=0,cnt=0;k<=n;k++,num++) {
                if(a[k]!=num) cnt++;
                dp[k][j+1]=min(dp[k][j+1],dp[i][j]+cnt);
            }
        }
    }

    for (int i=1; i<=n;i++) 
        cout << dp[n][i] << '\n';
}