c++) 8장 quantization (dp)

문제 : algospot.com :: QUANTIZE

algospot.com :: QUANTIZE

주의사항

1. 나열된 숫자들을 그룹화해서 풀어야하기 때문에, 미리 sort를 통해 정렬을 해주어야 합니다.

2. 각 그룹마다 오차 제곱의 합의 최솟값을 구해주는 방법이 필요합니다.

 

풀이과정

최적 부분 구조를 만족시키는 점화식을 생각해보면,

quantization(from,parts) 함수가 from번째 숫자에서 시작해서 parts개로 그룹화 했을 때 최솟값을 반환해준다고 할 때

=> {from~from+x-1 까지의 최솟값} + quantization(from+x,parts-1) 이 점화식이 될 수 있고,

해당 최솟값을 구하기 위한 방법으로는 미분식이 필요합니다.

 

 

최소해를 구하는 방법

우리가 a~b 구간에서 구하려는 오차 제곱의 합의 최소치를 구하기 위한 해를 m 이라고 한다면

이런 수식이 나올 것이고, 전개 후 m에 대해 미분하게 된다면

 

 

 

이런 수식이 될 것이며 우리가 찾는 m의 값은

이렇게 될 것입니다.

결국 a~b 구간의 평균이 우리가 찾는 최적의 값이 된다는 뜻이며

여기서 주의할 점은 m값이 정수이며, 우리가 찾는 m은 평균에 가장 가까운 값이어야 하므로

실수라고 가정하고 반올림해줘야 합니다. (그냥 나눈다면 답이 나오지 않습니다.)

 

이제 구한 m값을 가지고 맨 위의 수식에 대입한다면 a~b 구간의 최솟값이 구해지게 될 것입니다.

 

#include <iostream>
#include <stdio.h>
#include <algorithm>
#include <cstring>
#include <cmath>
#define INF 987654321
using namespace std;
int C,n,s;
int A[101];
int Sum[101],sqSum[101];
int cache[101][11];

int minians(int from, int to) {
    int sum = Sum[to] - (from == 0 ? 0 : Sum[from-1]);
    int sqsum = sqSum[to] - (from == 0 ? 0 : sqSum[from-1]);

    int m = round( (sum) / (to-from+1) );
    int result = sqsum - (2*m*sum) + (m*m*(to-from+1));
    return result;
}

void initial() {
    sort(A,A+n);
    memset(cache,-1,sizeof(cache));
    Sum[0] = A[0];
    sqSum[0] = A[0]*A[0];
    for(int i=1; i<n; i++) {
        Sum[i] = A[i] + Sum[i-1];
        sqSum[i] = A[i]*A[i] + sqSum[i-1];
    }
}

// from에서 시작해서 parts개로 양자화 했을 때 최소해를 반환
int quantization(int from ,int parts) {
    // 끝까지 도달했을경우
    if(from == n) return 0;
    // 더이상 양자화할 수 없다면
    if(parts == 0) return INF;

    int &ret = cache[from][parts];
    if(ret != -1) return ret;

    ret = INF;
    for(int step = 1; step+from <= n; step++) {
        ret = min(ret, minians(from,from+step-1)+quantization(from+step,parts-1));
    }
    return ret;
}

int main() {
    scanf("%d",&C);
    for(int i=0; i<C; i++) {
        scanf("%d %d",&n,&s);
        for(int j=0; j<n; j++) scanf("%d",&A[j]);
        initial();
        printf("%d\n",quantization(0,s));
    }
}