USACO 2016 Feb Gold 2 - Circular Barn Revisited

 USACO February 2016 Contest Gold 2번이다. BOJ 11994번에 등록되어 있으며 문제는 여기서 볼 수 있다.

문제 설명

 영어 디스크립션을 읽기 싫을 수도 있으니 대충 문제 설명을 하려고 한다. 첫째줄에 N과 K가 주어진다. N은 총 방의 갯수로 방은 중앙 정원을 기준으로 원형으로 둘러져 있다. 시계처럼 생각하면 된다. 소들은 모두 중앙에 있고, 우리는 그 중 잘 K개의 방문을 연다. 그 다음에는 N개의 숫자가 주어진다. 이는 최종적으로 1부터 N번방에 들어가야하는 소의 수이다. 소들은 열려진 방으로 들어가서 시계방향으로만 이동할 수 있다. 이때 소들의 이동거리의 합의 최솟값을 구하는 것이다.

예제 설명

위 링크의 예제에서 2번방돠 5번방을 열면 2,3,4번방에 가야하는 소들은 2번방으로 들어가고 5,6,1번 방에 가야하는 소들은 5번방으로 들어갈 것이다. 3번방에 갈 소 4마리는 1걸음, 4번방에 갈 소 2마리는 2걸음, 6,1번방에 갈 소 두마리씩은 각각 1걸음, 2걸음을 걸어야 하므로, 총걸은 거리는 4*1+2*2+1*2+2*2=14이고 이때가 최소이다.

문제 풀이

일단 기본적으로 dp일것 같다는 생각을 가지고 시작했다. 숫자의 범위가 n<=100 k<=7이기 때문에 고차원 DP일 것 같다는 생각을 했다. 그리고 확신을 가졌다. 소가 들어가서 배치하는 것이 아니라 배치된 상태에서 몇개의 방을 열어주어서 빼내는 것이라고 생각하자. 어떤 소가 가장 가까운 열린 방이 있다면 그 이후로 갈 이유는 없다. 즉 특정 시점까지에서 최솟값을 유지한다면 이는 그 후의 최솟값에 그대로 쓰인다는 것이다. 이는 정확히 DP가 쓰여야 할 조건과 맞는다. 

위의 상황을 조금 더 구체적으로 생각해보자. i방을 열어주었을 때 최솟값을 구하려는데, 이는 분명히 세부적인 부분이 존재한다. 몇 개의 방을 열었나와, 어느 방부터 시작해서 생각했나 이다. 이런식으로 생각하면 dp 배열을 만들 수 있다. 내가 만든 DP배열은 dp[i][j][k] = i번 방부터 j번 방까지의 소들을 그중 j번째 방을 포함해서 k개의 방을 열었을 때 소의 이동거리의 합의 최솟값이다. 위의 설명대로라면 i번째 방을 여는 것이 맞지만 시계,반시계를 햇갈려서 전체적으로 방향이 반대이다. 

이런식으로 DP 배열을 잡으니 BOJ 11006 - 파일 합치기가 생각이 났다. dp[i][j]를 i에서 j까지의 구간을 처리하는 값을 저장하고 있을 때 dp[i][j]를 i<=m<=j인 m에 대하여 dp[i][m]과 dp[m][j]를 가지고 연산한 값 중 최솟값을 선택하는 방식이다. 우리는 j번째 방을 열어 놓을 것이니 m을 그 전에 마지막으로 열어놓은 칸으로 설정하면 되겠다는 생각을 하였다.결과적으로 나온 dp식은  dp[s][e][l+1]=min(dp[s][e][l+1],dp[s][m][l]+dp[m+1][e][1]); 이다.

dp 배열의 사이즈는 k n^2 이고 한 칸을 채우는데 O(N)의 시간복잡도를 가진다. 따라서 총 시간복잡도는 O(KN^3)이 되어서 시간내에 해결할 수 있다.

구현 방식

일단 원형이기 때문에 dp[6][5]같은 것도 생각해야 하는데, 이는 처리하기 굉장히 까다롭다. 그래서 원형에 대해서 실제로 많이 사용하고, 나는 특히 많이 애용하는 방법인 배열 두배로 늘리는 기법을 사용했다. 따라서 6에서 시작해서 5로 끝나는 배열은 dp[6][n+5] 이런식이 될 것이다.

그 다음은 dp식을 적용하면 되는데 파일 합치기때 짰던 방식을 가지고 왔다. 구간의 size가 작은 dp칸 부터 채워나가는 방식이다. 이때 구간의 크기가 1인 dp칸은 미리 prefix sum을 저장하여 빠르게 채우는 방식을 선택하였다.

코드

#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
 
ll pre[1010];
ll arr[1010];
ll dp[202][202][8];
 
int main(){
    ll i,j,k,l,m,n,s,e,sz;
    scanf("%lld %lld",&n,&k);
    for(i=n;i>=1;i--){
        scanf("%lld",&arr[i]);
        arr[i+n]=arr[i];
    }
    for(i=1;i<=2*n;i++){
        pre[i]=pre[i-1]+arr[i];
    }
 
    for(i=1;i<=201;i++)
        for(j=1;j<=201;j++)
            for(l=1;l<=7;l++){
                dp[i][j][l]=1e18;
                if(i==j) dp[i][j][l]=0;
            }
 
    for(sz=1;sz<=n-1;sz++){
        for(s=1;s+sz<=2*n;s++){
            e=s+sz;
            dp[s][e][1]=dp[s][e-1][1]+pre[e-1]-pre[s-1];
            for(m=s;m<e;m++)
                for(l=1;l<k;l++)
                    dp[s][e][l+1]=min(dp[s][e][l+1],dp[s][m][l]+dp[m+1][e][1]);
        }
    }        
    ll ans=1e18;
    for(i=n;i<=2*n;i++){
        ans=min(ans,dp[i-n+1][i][k]);
    }
    printf("%lld",ans);
}