[C++] 알고스팟/동적계획법 - Quantization

문제 링크

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

algospot.com :: QUANTIZE

 

양자값과의 오차의 제곱을 구할 때 숫자마다 하나씩 양자값을 구하고 오차를 계산하는 것이 아닌

정렬된 숫자들을 적절하게 그룹으로 묶어서 각 그룹을 한 숫자로 표현해서 값을 찾아냅니다.

 

s개의 자연수를 사용해 양자화를 해야 하는데 숫자가 낮은 값에 낮은 s를 사용하고 높은 수에 비교적 더 높은 s를 사용해야 오차를 줄일 수 있습니다. 수열을 정렬하면 같은 s로 양자화되는 수가 인접해지므로 수를 정렬해줍니다.

 

그리고 정렬된 수열을 s가지 만큼의 그룹으로 묶어 값을 표현한 다음 각 그룹에서 나온 양자값과 그룹의 오차제곱을 구하고 모든 그룹에서 구한 오차의 합을 구해주면 됩니다.

 

 

구현 코드

 

	#include <iostream>
	#include <algorithm>
	#include <cstring>
	#define endl '\n'
	#define fastio cin.sync_with_stdio(false); cin.tie(nullptr)
	using namespace std;
	const int INF = 987654321;
	const int MAX = 101;
	int d[MAX][11];
	int A[MAX], pSum[MAX], pSqSum[MAX];
	int n, s;
	void precalc(){
	sort(A,A+n);
	pSum[0] = A[0];
	pSqSum[0] = A[0] * A[0];
	for(int i=1;i<n;i++){
	pSum[i] = pSum[i-1] + A[i];
	pSqSum[i] = pSqSum[i-1] + A[i] * A[i];
	}
	}
	//A[lo..hi] 구간을 하나의 숫자로 표현할 때 최소 오차 합을 계산한다.
	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 = d[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(){
	fastio;
	int _;
	cin >> _;
	while(_--){
	memset(d, -1, sizeof(d));
	cin >> n >> s;
	for(int i=0;i<n;i++)
	cin >> A[i];
	precalc();
	cout << quantize(0,s) << endl;
	}
	return 0;
	}

view raw quantize.cpp hosted with ❤ by GitHub