문제링크 입니다

손도 대지못했습니다 ㅜ^ㅜ. 양자화 라는 말은 들어봤는데,,,,, 힘들었습니다. 문제집을 참고했습니다.

[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