QUANTIZE (중하, p. 244)

난이도가 ‘중’으로 되어있었지만, 어렵진 않았던 문제 → 그래서 ‘중하’로 낮춤.

N개의 숫자들을 정렬한 다음, 아래의 2가지 memoization이 필요하다.

lp[b][e] = index [b,e] 구간을 숫자 1개로 양자화 할 때 $\sum(오차^{2})$의 최소 값
dp[x][s] = index x까지 s개로 양자화 → 점화식: dp[x][s] = dp[i][s-1] + lp[i][x] (단, 0<i<x)

#include <bits/stdc++.h>
using namespace std;
int v[101];
int dp[101][11];
bool chk[101][11];
const int INF = 0x3f3f3f3f;
int lp[101][101];
int GetMinSqSum(int b, int e) {
    if(b == e) return 0;
    int& ret = lp[b][e];
    if(ret >= 0) return ret;

    ret = INF;
    for(int i = v[b]; i <= v[e]; i++) {
        int sum = 0;
        for(int j = b; j <= e; j++) {
            sum += (v[j] - i) * (v[j] - i);
        }
        ret = min(ret, sum);
    }
    return ret;
}
int f(int x, int s) {
    if(x == 0 && s >= 0) return 0;
    else if(s < 0) return INF;

    int& ret = dp[x][s];
    if(chk[x][s]) return ret;
    chk[x][s] = true;

    if(s == 1) return ret = GetMinSqSum(1, x);

    ret = INF;
    for(int i = x; i >= 1; i--) {
        ret = min(ret, GetMinSqSum(i, x) + f(i - 1, s - 1));
    }
    return ret;
}
int main() {
    ios::sync_with_stdio(false); cin.tie(0);
    int tc; cin >> tc;
    while(tc--) {
        int n, s; cin >> n >> s;
        for(int i = 1; i <= n; i++) {
            cin >> v[i];
        }
        sort(v + 1, v + n + 1);
        memset(chk, false, sizeof(chk));
        memset(lp, -1, sizeof(lp));

        printf("%d\n", f(n, s));
    }

    return 0;
}