알고스팟 Quantization

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

algospot.com :: QUANTIZE

 

 

 

 

 

<접근방법>

완탐으로는 도저히 풀 수 없음은 조금만 생각해보면 알 수 있다.

그럼 어떻게 할까?

일단 관찰을 해보자.

1,2,3,4,5,6,7,8,9,.... 이렇게 숫자가 오름차순으로 있다고 가정했을 때,

같은 양자화 값을 갖는다는 것은 서로 가까이에 있음을 의미한다.

그러므로 수열을 정렬을 한 후에, 잘 쪼개면 최적의 값을 얻을 수 있음을 의미한다.

이것은 dp로 탐색해보면 되겠다.

그럼 양자화의 값은 어떻게 정할까?

오차제곱의 합의 식을 유도를 하던가 혹은 직관적으로 같은 덩어리인 수들의 평균값이 양자화의 값이

되어야함을 알 수 있다.

(책에는 더 빨리 푸는 방법이 있으나 잠시 미루어두었습니다..^^)

 

---

 

 

 

<코드>

#include <iostream>
#include <algorithm>
#include <memory.h>
using namespace std;

const int INF = 987654321;
int tc, n, m;
int a[101], cache[101][11];

//from부터 to(포함)까지의 최소오차제곱합
//최소오차제곱합은 묶음 안의 숫자들의 평균으로 구한다
int minError(int from, int to) {
	int sz = to - from + 1;
	int sum = 0;
	for (int i = from; i <= to; i++) {
		sum += a[i];
	}

	int avg = (int)(0.5 + (double)sum/sz);

	int res = 0;
	for (int i = from; i <= to; i++) {
		int t = abs(avg - a[i]);
		res += t * t;
	}

	return res;
}

//x에서 끝까지 묶은 다음에 최소의 오차제곱합을 출력
int quantize(int from, int parts) {
	//기저사례 : 모든 수를 다 양자화 했을 때
	if (from == n) return 0;
	//기저사례 : 모든 수를 다 양자화 하지 않았음에도 더 이상 묶음보따리가 남아있지 않을 때
	if (parts == 0) return INF;
	//보따리를 다 쓰지 않아도 되는 것에 유의한다

	//중복방문
	int &res = cache[from][parts];
	if (res != -1) return res;

	//계산
	//묶기
	//여기서 만들 묶음의 사이즈를 결정해보자
	//사이즈의 범위를 보자.
	//최소 1이고 최대 n
	res = INF;
	for (int size = 1; from + size <= n; size++) {
		res = min(res, minError(from, from+size-1) + quantize(from+size, parts-1));
	}

	//리턴
	return res;
}

int main() {
	ios_base::sync_with_stdio(false);
	cin.tie(NULL);
	cout.tie(NULL);

	cin >> tc;
	while (tc--) {
		memset(cache, -1, sizeof(cache));

		cin >> n >> m;
		for (int i = 0; i < n; i++) {
			cin >> a[i];
		}

		sort(a, a + n);

		cout << quantize(0, m) << '\n';
	}

	return 0;
}

 

 

---

 

 

<느낀 점>

1. 형식을 강제해서 우리가 아는 알고리즘으로 만들 수 있게 하는 것.

수학 공식 유도 같다는 생각을 했다.

 

2. int avg = (int)(0.5 + (double)sum/sz);

반올림을 이렇게 구현한다.

 

 

 

 

 

 

 

 

[참고]

-프로그래밍 대회에서 배우는 알고리즘 문제해결전략1