SCPC 2016 본선 A. 재활용

https://www.codeground.org/practice/practiceProbView.do?probId=36

\(1\leq{M}\leq{N}\leq{500}\)

N은 집의 개수 M은 재활용 쓰레기 통의 개수.

수직선상의 N개의 집의 좌표가 주어질 때 M개의 쓰레기통을 적절히 배치하여

각 집에서 가장 가까운 쓰레기통까지의 거리의 합이 최소가 되도록 하고 싶을 때 이 최소값을 구하는 문제이다.

일단 거리의 합이아니라 거리의 최대값이 최소가 되도록 하는 문제 같은 경우에는

바이너리 서치(파라메트릭서치)로 풀 수가있다. 

그리고 이 문제는 dp로 풀 수 있다. 우선 몇가지 정의를 하자. (모든 집들은 좌표로 오름차순 정렬되어있다고 가정)

\(X[i]\) : i번째 집의 좌표

\(C[i][j]\) : i번째 집부터 j번째 집까지 하나의 쓰레기통으로 카바할 때 각 집에서 이 쓰레기통까지의 거리의 합의 최소값

\(D[i][j]\) : 왼쪽부터 i 개의 집을 j개의 쓰레기통으로 카바할 때 각 집에서 가장 가까운 쓰레기통까지의 거리의 합의 최소값

일때, 두가지 점화식이 나온다.

\(C[i][j]=C[i][j-1]+X[j]-X[i+(j-i)/2]\) 

\(D[i][j]=\min_{k\leq{i}}(D[i][j-1]+C[i-k+1][i])\)

점화식에 대해 설명하자면 우선 첫번째거는 i~j-1 집을 카바하는 상태에서 오른쪽에 하나가 추가되면,

추가되기 전에 홀수개의 집을 카바중이었다면 쓰레기통 위치는 그대로놓고 새집과 쓰레기통과의 거리만 더해도 최적해가되고

(짝수개일땐 가운데 점이 두개이기 때문에 둘중 어디에 놔도 최적해)

추가되기 전에 짝수개의 집을 카바중이었다면 쓰레기통의 위치를 가운데 두 점중에 오른쪽에 놓으면 새로 추가했을 때

이 점이 유일한 가운데 점이 되기 때문에 역시 새로 추가되는 집과 이 쓰레기통과의 거리를 구하면 되기 때문에

새로 집을 추가하기 전에 쓰레기통의 위치만 잘 잡으면 이 것과 새 집의 거리만 추가되는데 이 잘 잡은 위치가 바로

i+(j-i)/2 이다. 그냥 쉽게말해서 홀수개면 가운데점, 짝수개면 가운데두점중 오른쪽점에 쓰레기통을 두었었다고 가정하면

직관적으로 이해하기 쉽다.

두번째 점화식은 왼쪽부터 i개의 집을 j개의 통으로 카바하는 최적해는 j개중에 마지막에 놓는 쓰레기통이

마지막에 있는 몇개의 집을 카바하는지, 즉 i개의 집중 오른쪽 끝에있는 몇개의 집이나 마지막 쓰레기통에 버리러 가는지를

고정해주고 마지막 쓰레기통이 카바하는 집의 개수를 모두 봐주면서 최소값을 구하면 된다.

이 문제는 그니까 N개의 집들을 M개의 그룹으로 나눠서 M개의 쓰레기 통을 각 그룹에 배정해주는 것과 같은 문제이다.

#include <bits/stdc++.h>
using namespace std;
const int MOD = 1e9+7;
const int INF = 0x3c3c3c3c;
const long long INFL = 0x3c3c3c3c3c3c3c3c;
 
int T;
int M, N;
int distSum[503][503];
int dp[503][503];
int home[503];
 
int main() {
    scanf("%d",&T);
    for(int t = 1; t <= T; t++){
        memset(dp, 0x3c, sizeof(dp));
        memset(distSum, 0, sizeof(distSum));
 
        scanf("%d%d", &N, &M);
        for(int i = 1 ; i <= N; i++){
            scanf("%d", home+i);
        }
        sort(home+1, home+1+N);
 
        for(int i = 1 ; i <= N; i++){
            for(int j = i ; j <= N; j++){
                distSum[i][j] = distSum[i][j-1] + home[j] - home[i + (j-i)/2];
            }
        }
        for(int i = 0 ; i <= M; i++) dp[0][i] = 0;
        
        for(int i = 1 ; i <= N; i++){
            for(int j = 1 ; j <= M; j++){
                for(int k = 1 ; k <= i; k++){
                    dp[i][j] = min(dp[i][j], dp[i-k][j-1] + distSum[i-k+1][i]); 
                }
            }
        }
 
        printf("Case #%d\n%d\n", t, dp[N][M]);
    }
    return 0;
}