[종만북 문제] Quantization (문제 ID : QUANTIZE, 난이도 : 중)

프로그래밍 대회에서 배우는 알고리즘 문제해결 전략(이하 종만북)에서 소개된 문제를 풀이합니다. 알고리즘에 진심이시라면, 직접 구매하셔서 읽어보시는 것을 추천합니다!

---

핵심 :

1. 최적 부분 문제를 찾는 것은 간혹, 매우 쉽지 않은 일이다... 무식하게 푸는 전법부터 시작하면 큰코가 다칠 수 있다. 근데 나 코 낮은데.. 어쨌든 다쳤다.

---

[종만북 문제] Quantization (문제 ID : QUANTIZE, 난이도 : 중)

이 문제는 아이디어가 필요하다. 단순히 수열을 정렬한 다음에, 숫자를 최솟값에서 최댓값까지 넣는 방식으로는 풀 수 없기 때문이다.

그런데 이렇게 묶어보면 어떨까?

이렇게 묶어 놓고 보면, 인접한 숫자끼리 적절히 묶고, 최소 오차를 내는 수를 찾는 문제로 변형할 수 있다!

그럼 아래와 같이 점화식을 세워볼 수 있는데...

minError 는 한 묶음 내에서 오차를 구하는 함수이다. from 은 시작 지점, parts 는 사용 가능한 남은 양자화 숫자의 수를 의미한다.

 

그렇다면 minError 는 어떻게 구할 수 있을까?

위처럼 식을 세울 수 있는데... 2차함수니까, 미분을 통해 최솟값을 구하면 될 것이다(미분값이 0 인 지점).

 

또한, 부분합의 경우 아래의 원리를 이용하면 된다 : 

부분합 누적 수열을 구하고, 구간을 구할 때 끝 인덱스 값에서 시작 인덱스 값을 빼주기만 하면 된다. 😉

 

따라서 위의 내용을 전부 적용하면, 아래와 같이 코드를 구현할 수 있다! 😊

#include <iostream>
#include "stdlib.h"
#include <cmath>
#include <vector>
#include <map>
#include <algorithm>

using namespace std;

/****************************************************************************************************/

const int INF = 987654321;

// A[] : 양자화해야 할 수열, 정렬한 상태
// pSum[] : A[] 의 부분합을 저장한다. pSum[i] 는 A[0] .. A[i] 의 합
// pSqSum[] : A[] 제곱의 부분합을 저장한다. pSqSum[i] 는 A[0]^2 .. A[i]^2 의 합
int n;
int s;
int A[101], pSum[101], pSqSum[101];

int cache[101][11];

// 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];
	}
}

// A[lo] ... A[hi] 구간을 하나의 숫자로 표현할 때 최소 오차 합을 계산한다.
int minError(int lo, int hi)
{
	// 부분합을 이용해 A[lo] ~ A[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));

	// sum(A[i] - m)^2 전개한 결과를 부분 합으로 표현
	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 = 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;
}

void inputHandler()
{
	cin >> n;
	cin >> s;

	for (int i = 0; i < n; ++i)
	{
		cin >> A[i];
		pSum[i] = 0;
		pSqSum[i] = 0;

		for (int j = 0; j <= s; ++j)
			cache[i][j] = -1;
	}

	precalc();
}

int main()
{
	int cases;
	cin >> cases;
	while (cases--)
	{
		inputHandler();

		cout << quantize(0, s) << endl;
	}

	return 0;
}