Treejin's Note

문제 설명

• 1000이하의 자연수들로 구성된 수열이 주어진다.
• 최대 S종류의 값을 사용해 양자화하려고 한다.
• S는 1이상 10이하이다.
• 양자화되는 숫자는 원래 수열에 없는 숫자일 수도 있다.
• 오차 : 수열의 원래 숫자와 양자화되는 숫자의 차이

=> 가능한 오차 제곱의 합의 최솟값 구하기

문제 풀이

1 2 3 4 5 라는 수열이 있을 때 이를 한 종류로 양자화한다고 하면

오차 제곱의 합은 평균값인 3으로 양자화를 했을 때 가장 작다.

그렇다면, S종류로 양자화를 한다고 하면

수열을 S개의 묶음으로 분류한 후

각 묶음의 평균값으로 오차 제곱의 합을 구하면 된다.

즉, 어떻게 묶느냐에 따라서 오차 제곱의 합이 달라진다.

또한 묶음을 만들 땐 비슷한 숫자끼리 묶는 것이

가장 평균과의 오차를 줄일 수 있는 방법이므로

1 5 2 4 3과 같이 뒤죽박죽된 수열을 정렬한 후

묶는 것이 연산이 간단하다.

코드는 다음과 같은 흐름으로 진행된다.

1. 수열 정렬하기
2. 모든 묶음 경우의 수의 최소 오차 제곱의 합 구하기
3. 오차제곱의 합들의 최소 조합 구하기

3번에서 메모이제이션을 활용해 index 번째의 남은 조합 개수(remainCombCnt)일 때의 계산 결과를 저장하고,

이후 중복되는 연산이 필요할 때 활용하도록 했다.

문제 풀이 코드

#include <iostream>
#include <string.h>

#define MAX 999999999;

using namespace std;

int arr[100];
int temp[100];
int N, S;
int minError[100][100];
int minComb[100][11];

void sort(int start, int mid, int end) {
	int a = start;
	int b = mid + 1;
	int index = start;

	while (a <= mid && b <= end) {
		if (arr[a] < arr[b]) {
			temp[index++] = arr[a++];
		}
		else {
			temp[index++] = arr[b++];
		}
	}

	while (a <= mid) {
		temp[index++] = arr[a++];
	}

	while (b <= end) {
		temp[index++] = arr[b++];
	}

	for (int i = start; i <= end; ++i) {
		arr[i] = temp[i];
	}
}

// 정렬
void mergeSort(int start, int end) {
	if (start >= end)
		return;

	int mid = (start + end) / 2;
	mergeSort(start, mid);
	mergeSort(mid + 1, end);
	sort(start, mid, end);
}

// 오차 합 구하기
int getErrorSize(int startIndex, int endIndex, int quantiNum) {
	int result = 0;
	for (int i = startIndex; i <= endIndex; ++i) {
		int sub = arr[i] - quantiNum;
		result += (sub * sub);
	}
	return result;
}

// startIndex ~ (startIndex ~ N) 까지인 영역의 최소 오차합 구하기
void calculateMinError(int startIndex) {
	int sum = 0;
	for (int endIndex = startIndex; endIndex < N; ++endIndex) {
		sum += arr[endIndex];
		int average = (((sum * 10) / (endIndex - startIndex + 1)) + 5) / 10;	// 평균 구하기(반올림 포함)
		minError[startIndex][endIndex] = getErrorSize(startIndex, endIndex, average);
	}
}

// 오차합들의 최소 조합 구하기
int findMinErrorComb(int index, int remainCombCnt) {
	if (index >= N)	// 최대 S개의 수
		return 0;
	int& ret = minComb[index][remainCombCnt];
	if (ret != -1)	// 이미 계산된 결과
		return ret;
	if (remainCombCnt == 1) {	// 남은 묶음이 한묶음이라면
		return ret = minError[index][N - 1];
	}
	ret = MAX;
	for (int i = index; i < N; ++i) {
		int value = minError[index][i] + findMinErrorComb(i + 1, remainCombCnt - 1);
		ret = ret > value ? value : ret;
	}
	return ret;
}


int main() {
	int C;
	cin >> C;
	for (int tc = 1; tc <= C; ++tc) {
		memset(minComb, -1, sizeof(int) * 100 * 11);
		cin >> N >> S;
		for (int i = 0; i < N; ++i) {
			cin >> arr[i];
		}

		// 정렬
		mergeSort(0, N - 1);

		// 범위에 따른 최소 오차 찾기
		for (int i = 0; i < N; ++i) {
			calculateMinError(i);
		}
		
		// 범위 조합하기
		cout << findMinErrorComb(0, S) << endl;
		
	}
	return 0;
}