USACO 2018 Feb Gold 3 - Taiming the Herd

 USACO 2018 February Gold 3번이다. BOJ 15747번에 등록되어 있으며 문제는 여기서 볼 수 있다.

문제 설명

문제해석과 이해가 굉장히 어려운 문제다. N이 주어지고 우리는 총 N개를 k개의 그룹으로 나눠야 한다.
이때 나눈 그룹별로 숫자가 0부터 1씩 올라가며 부여된다. 예를 들어 9를 4 3 2로 분할 했다면, (0,1,2,3)(0,1,2)(0,1)이 된다. 이때 분할 후에 매겨진 값으로 만들어진 배열이 주어진 배열과 최소 몇 개가 다른지 n 이하의 모든 k에 대해서 출력해야 한다.

예제를 예시로 들자면 1개의 그룹은 무조건 0,1,2,3,4,5로 1,2 만 같습니다. 2개의 그룹으로 나눌 때는 0,1,2,3 0,1 로 나누어야 다른 원소가 2개로 가장 적습니다. 3개의 그룹으로 나눌 때는 0,1,2 0 0,1 로 나누어야 다른 원소가 1개로 가장 적습니다. 

문제 풀이

굉장히 무난한 다차원 DP 문제이다. dp[i][j]를 배열의 i번째 항까지 비교하며 j개의 그룹으로 나누었을 때 다른 원소의 최소 갯수라고 하자. 그러면 dp[i][j]는 i보다 작은 k에 대하여 dp[k][j-1]+(k+1부터 i 까지 배열과 다른 원소의 갯수) 중 최솟값이 된다. dp 테이블의 크기는 N^2 이고 한 칸을 채우는 데 O(N)이 걸리므로 총 시간 복잡도는 O(N^3)다.

코드 

작성한 코드는 dp[i][j][k]로 잡아서 i부터 j까지 k개의 그룹으로 나누는 것으로 정의하였다.

 

#include<bits/stdc++.h>
using namespace std;
typedef long long int ll;
 
ll dp[201][201][201];
ll arr[1010101];
 
int main(){
    ll i,j,k,l,m,n;
    scanf("%lld",&n);
    for(i=1;i<=n;i++)
        scanf("%lld",&arr[i]);
 
    for(i=1;i<=n;i++)
        if(arr[i]==0) dp[i][i][1]=1;
 
    for(i=1;i<n;i++){
        for(j=1;j+i<=n;j++){
            dp[i][i+j][1]=dp[i][j+i-1][1];
            if(j==arr[i+j])
                dp[i][i+j][1]++;
        }
    }
 
    for(k=2;k<=n;k++){
        for(i=1;i<n;i++){
            for(j=1;j+i<=n;j++){
                for(l=i+k-2;l<i+j;l++){
                    dp[i][i+j][k]=max(dp[i][i+j][k],dp[i][l][k-1]+dp[l+1][i+j][1]);
                }
            }
        }
    }
 
    for(i=1;i<=n;i++)
        printf("%lld\n",n-dp[1][n][i]);
}