[algospot] Quantization (c++)

출처 : algospot.com :: QUANTIZE

algospot.com :: QUANTIZE

풀이 방법

정렬이 중요한 문제이다. 문제가 안 풀릴 시 정렬을 한번 생각해 보자

재귀 호출시 인자로 시작점과 남은 구간 자르기 횟수를 넘겨주면 된다

오차 제곱의 합을 구할 때 구간에서 평균값을 채택하면 구할 수 있다.

오차 제곱의 합의 값 계산은 구간 합 - 2 * 평균 * 구간 합 + 평균 * 평균 *(hi -lo +1)을 해주면 된다

여기서 hi 와 lo는 구간의 처음과 끝의 인덱스를 뜻한다.

#include <iostream>
#include <algorithm>
#include <memory.h> 
#include <vector>

using namespace std;

const int INF = 987654321;

int dp[101][11], n;
int num[101], pSum[101], pSqSum[101];

void precalc() {
	sort(num, num + n);
	pSum[0] = num[0];
	pSqSum[0] = num[0] * num[0];
	for (int i = 1; i < n; i++) {
		pSum[i] = pSum[i - 1] + num[i];
		pSqSum[i] = pSqSum[i - 1] + num[i] * num[i];
	}
}

int minError(int lo, int hi) {
	int sum = pSum[hi] - (lo == 0 ? 0 : pSum[lo - 1]);
	int sqSum = pSqSum[hi] - (lo == 0 ? 0 : pSqSum[lo - 1]);
	int m = int(0.5 + (double)sum / (hi - lo + 1));
	int ret = sqSum - 2 * m * sum + m * m * (hi - lo + 1);
	return ret;
}

int quantize(int from, int parts) {
	//기저 사례
	if (from == n) return 0;
	if (parts == 0) return INF;
	int& ret = dp[from][parts];
	if (ret != -1) return ret;
	ret = INF;
    // 조각의 길이를 늘려가며 최소치를 찾는다.
	for (int partSize = 1; from + partSize <= n; partSize++) {
		ret = min(ret, minError(from, from + partSize - 1) + quantize(from + partSize, parts - 1));
	}
	return ret;
}

int main(void) {
	int C;
	cin >> C;
	while (C--) {		
		memset(dp, -1, sizeof(dp));
		memset(pSum, 0, sizeof(pSum));
		memset(pSqSum, 0, sizeof(pSqSum));
		int s, value;
		cin >> n >> s;
		for (int i = 0; i < n; i++) {
			cin >> value;
			num[i] = value;
		}
		precalc();
		cout << quantize(0, s) << endl;
	}
	return 0;
}