손도 대지못했습니다 ㅜ^ㅜ. 양자화 라는 말은 들어봤는데,,,,, 힘들었습니다. 문제집을 참고했습니다.
[QUANTIZE] 문제 😭😭😭😭😭
Quantization (양자화) 과정은, 더 넓은 범위를 갖는 값들을 작은 범위를 갖는 값들로 근사해 표현함으로써 자료를 손실 압축하는 과정을 말한다. 예를 들어 16비트 JPG 파일을 4컬러 GIF 파일로 변환하는 것은 RGB 색 공간의 색들을 4컬러 중의 하나로 양자화하는 것이고, 키가 161, 164, 170, 178 인 학생 넷을 ‘160대 둘, 170대 둘’ 이라고 축약해 표현하는 것 또한 양자화라고 할 수 있다.
1000 이하의 자연수들로 구성된 수열을 최대 S종류 의 값만을 사용하도록 양자화하고 싶다. 이 때 양자화된 숫자는 원래 수열에 없는 숫자일 수도 있다. 양자화를 하는 방법은 여러 가지가 있다. 수열 1 2 3 4 5 6 7 8 9 10 을 2개의 숫자만을 써서 표현하려면, 3 3 3 3 3 7 7 7 7 7 과 같이 할 수도 있고, 1 1 1 1 1 10 10 10 10 10 으로 할 수도 있다. 우리는 이 중, 각 숫자별 오차 제곱의 합을 최소화하는 양자화 결과를 알고 싶다.
예를 들어, 수열 1 2 3 4 5 를 1 1 3 3 3 으로 양자화하면 오차 제곱의 합은 0+1+0+1+4=6 이 되고, 2 2 2 4 4 로 양자화하면 오차 제곱의 합은 1+0+1+0+1=3 이 된다.
수열과 S 가 주어질 때, 가능한 오차 제곱의 합의 최소값을 구하는 프로그램을 작성하시오
입력
입력의 첫 줄에는 테스트 케이스의 수 C (1 <= C <= 50) 가 주어진다. 각 테스트 케이스의 첫 줄에는 수열의 길이 N (1 <= N <= 100), 사용할 숫자의 수 S (1 <= S <= 10) 이 주어진다. 그 다음 줄에 N개의 정수로 수열의 숫자들이 주어진다. 수열의 모든 수는 1000 이하의 자연수이다.
출력
각 테스트 케이스마다, 주어진 수열을 최대 S 개의 수로 양자화할 때 오차 제곱의 합의 최소값을 출력한다.
입력 예제
2
10 3
3 3 3 1 2 3 2 2 2 1
9 3
1 744 755 4 897 902 890 6 777
출력 예제
0
651
전체 코드는 다음과 같습니다.
//
// QUANTIZE.cpp
// AALGGO
//
// Created by inhyeok on 2021/09/23.
//
#include <iostream>
#include <fstream>
#include <algorithm>
#include <vector>
#include <cstring>
using namespace std;
ifstream fin("QUANTIZE.txt");
int cache[100][10];
int n;
int arr[100];
int pSum[100]; // 부분 합 arr[0] + ... arr[i]
int pSqSum[100]; // 제곱근 부분 합 arr[0]^2+...arr[i]^2
const int INF = 987654321;
// 정렬 하고 부분합들 계산하는 함수.
void precalc(){
sort(arr, arr+n);
pSum[0] = arr[0];
pSqSum[0] = arr[0] * arr[0];
for(int i =1; i<n; i++){
pSum[i] = pSum[i-1] + arr[i];
pSqSum[i] = pSqSum[i-1] + (arr[i] * arr[i]);
}
}
// arr[low]...arr[high] 구간을 하나의 숫자로 표현할 때 최소 오차 합 계산
int minDiffrence(int low, int high)
{
// 부분합을 이용해 arr[low]...arr[high]의 합 구함
int sum = pSum[high] - (low == 0 ? 0 : pSum[low - 1]);
int squareSum = pSqSum[high] - (low == 0 ? 0 : pSqSum[low - 1]);
//평균을 반올림한 값으로 이 수들을 표현
int mean = (int)(0.5 + (double)sum / (high - low + 1)); //반올림
// sum(arr[i]-mean)^2를 전개한 결과를 부분합으로 표현
// ∑(arr[i]-mean)^2 = (high-low+1)*mean^2 - 2*(∑arr[i])*mean + ∑arr[i]^2
int result = squareSum - (2 * mean*sum) + (mean*mean*(high - low + 1));
return result;
}
int QUANT(int from, int parts){
//기저 사례:모든 숫자를 다 양자화했을 때
if (from == n)
return 0;
//기저 사례 : 숫자는 아직 남았는데 더 묶을 수 없을 때 아주 큰 값 반환
if (parts == 0)
return INF;
int &result = cache[from][parts];
if (result != -1)
return result;
result = INF;
//조각의 길이를 변화시켜 가며 최소치 찾음
for (int partSize = 1; from + partSize <= n; partSize++)
result = min(result, minDiffrence(from, from + partSize - 1) + QUANT(from + partSize, parts - 1));
return result;
}
int main(int argc, const char * argv[]) {
int Test_case;
fin >> Test_case;
for (int i=0; i< Test_case ; i++){
int s;
fin >> n;
fin >> s;
memset(cache,-1,sizeof(cache));
for(int j=0; j<n; j++){
fin >> arr[j];
}
precalc();
cout << QUANT(0,s) << endl;
}
return 0;
}
Comments