동적 계획법 - 7. Quantization

문제 : Qunatization (난이도 : 中)

 

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

 

 분석

양자화를 하는 데 있어 다음과 같은 규칙이 있다.

같은 수로 양자화되는 숫자들은 인접한 숫자들이다.

따라서 일단 입력된 수열을 크기순으로 정렬을 할 필요가 있다.

 

from번째 이후의 숫자들을 parts개의 묶음으로 묶을 때, 최소 오류 제곱 합을 반환하는 함수를 quatize(from, parts)라 하자.

a번째 수부터 b번째 수까지 하나의 수로 표현했을 때의 최소 오류를 반환하는 함수를 minError(from, from+size-1)라 하자.

 

그럼 다음과 같은 점화식이 성립된다.

quantize(from, parts) = min[ minError(from, from+size-1) + quatize(from+size, parts-1) ] (단, size는 1 ~ n-from)

 

minError()를 구현하는 데 있어 무식하게 해도 되지만 미분을 이용하면 좀 더 빠르게 구할 수 있다.

옆 식을 m에 대해 미분을 해서 최솟값을 찾게 되면 모든 값의 평균이 나오게 된다.

여기서 평균을 구할 때 통상 O(n)의 시간이 걸리지만, 부분 합을 이용하게 되면 O(1)로 계산할 수 있다.

부분 합은 쉽게 확률과 통계에 나오는 CDF(Cumlative Distribution Function)로 생각하면 된다.

 

부분 합은

 

로 정의할 수 있다. 따라서 A[a]부터 A[b]까지의 합을 다음과 같이 구할 수 있다.

 

 

A[a] ~ A[b] 까지의 합

 

 구현

const int INF = 987654321;
//A[] 양자화해야할 수열, 정렬된 상태
//pSum[] : 부분 합, pSqSum[] : 제곱 부분 합
int A[101], pSum[101], pSqSum[101];
int n, s;

//A를 정렬하고 부분 합을 계산한다.
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];
	}
}

//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]);
	//average는 반올림한 값으로 표현한다.
	int m = int(0.5 + (double)sum / (hi - lo + 1));
	//sum (A[i]-m)^2 전개 후 계산
	int ret = sqSum - 2 * m*sum + m * m*(hi - lo + 1);
	return ret;
}

int cache[101][11];
int quantize(int from, int parts)
{
	//base case. 모든 수를 다 양자화 했을 때
	if (from == n) return 0;
	//base case. 숫자는 남았지만 더 묶을 수 없을 때 매우 큰 수를 반환한다.
	if (parts == 0) return INF;
	//memoization
	int& ret = cache[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()
{
	int c;
	cin >> c;
	while (c--)
	{
		memset(cache, -1, sizeof(cache));
		cin >> n >> s;
		for (int i = 0; i < n; i++)
		{
			cin >> A[i];
		}
		precalc();
		cout << quantize(0, s) << '\n';
	}
	return 0;
}