알고스팟 - QUANTIZE

https://algospot.com/judge/problem/read/QUANTIZE

사용할 숫자의 개수를 "그룹의 개수"라 생각했다. 한 그룹에서 오차의 합이 최소가 되려면 그룹의 평균을 기준(양자화하는 숫자)으로 잡아야한다.

모듈화를 제대로 못해서 코딩이 계속 꼬였다. 다음부터는 함수로 적절히 쪼개서 문제를 푸는 데 방해되지 않도록 해야겠다.

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

typedef long long lld;

#define INF 987654321

int sum[105];       // 누적 합
int err[105][105];  // [a, b] 에서 나오는 오차 제곱의 합
int arr[105], n, s;

int minError(int a, int b){
    int psum = sum[b]-sum[a-1];
    int aver = psum/(b-a+1.)+.5;
    int ret = 0;
    for(int i=a; i<=b; ++i) ret += (aver-arr[i])*(aver-arr[i]);
    return ret;
}

int dp[102][11];
int f(int pos, int rs /* 남은 개수 */){
    if(pos > n) return 0;
    if(rs >= s) return INF;
   
    int& r = dp[pos][rs];
    if(r != -1) return r;
    r = INF;
    for(int i=pos; i<=n; ++i){
        r = min(r, err[pos][i] + f(i+1, rs+1));
    }
    return r;
}

int main(){
    int T;
    scanf("%d", &T);
    while(T--){
        memset(dp, -1, sizeof(dp));
        memset(sum, 0, sizeof(sum));
        memset(err, 0, sizeof(err));
       
        scanf("%d %d", &n, &s);
        for(int i=1; i<=n; ++i) scanf("%d", &arr[i]);
        sort(arr+1, arr+n+1);
        for(int i=1; i<=n; ++i){
            sum[i] += sum[i-1] + arr[i];
        }
        for(int i=1; i<=n; ++i){
            for(int j=i; j<=n; ++j){
                err[i][j] = minError(i, j);
            }
        }
        printf("%d\n", f(1, 0));
    }
    return 0;
}