QUANTIZE - Quantization (dp, 전처리, 수학)

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

 

<문제설명>

최대 100개의 숫자 배열이 주어진다. 최대 10개의 대표 정수를 정해서(배열에 없는 값 허용) 오차 제곱의 합의 최소치를 구하는 문제.

 

<풀이>

오차 제곱의 합이 최소가 되도록 하려면 대표값을 각 집합의 평균으로 정해야 한다. (식을 미분하면 알 수 있다)

 

 

입력받은 배열을 오름차순 정렬하면, 인접한 두 숫자는 같은 대표값을 갖거나 다른 대표값을 갖는 집합의 경계이다.

 

 

f(k,e,t) : k이후, 이번 집합의 처음 인덱스 e, 여태까지 분류한 집합의 수 t에 대해 오차 제곱의 합의 최소를 반환

 

배열의 각 숫자마다 두개의 선택지가 있다. 새로 집합만들어 그 집합의 첫번째 원소가 되거나 기존 집합에 포함되거나.

 

cost(l,r) 을 a[l,r] 오차 제곱의 합이라고 할때, 다음과 같이 점화식이 나온다. 기저만 잘 처리해주자

 

<코드>

typedef long long ll;
const int MAX = 1e2 + 2;

ll dp[MAX][MAX][11], n, s, a[MAX], psum[MAX], psum2[MAX];

ll f(int k, int e, int t) {
	if (k == n) {
		ll p = ll(0.5 + double(psum[k] - psum[e]) / (k - e));
		ll temp = psum2[k] - psum2[e] - 2 * p * (psum[k] - psum[e]) + p * p * (k - e);
		return temp;		
	}

	ll& ret = dp[k][e][t];
	if (ret != -1) return ret;

	ret = f(k + 1, e, t);
	if (t < s && k!=0) {
		ll p = ll(0.5+ double(psum[k] - psum[e]) / (k - e));
		ll temp = psum2[k] - psum2[e] - 2 * p * (psum[k] - psum[e]) + p * p * (k - e);
		ret = min(ret, temp + f(k + 1, k, t + 1));
	}
	return ret;
}

int main() {
	FAST;
	int tt; cin >> tt;
	while (tt--) {
		memset(dp, -1, sizeof(dp));
		memset(psum, 0, sizeof(psum));
		memset(psum2, 0, sizeof(psum2));

		cin >> n >> s;
		for (int i = 0; i < n; i++) cin >> a[i];
		sort(a, a + n);
		for (int i = 0; i < n; i++) {
			psum[i + 1] = psum[i] + a[i];
			psum2[i + 1] = psum2[i] + a[i] * a[i];
		}
		
		cout << f(0, 0, 1) << '\n';
	}
}

 

<생각>

오차 제곱의 합을 식으로 잘 쓰면, 제곱의 구간합, 일반 구간합으로 O(1)에 cost를 구할 수 있다.