[동적계획법] 7. Quantization

 

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

algospot.com :: QUANTIZE

 

 

컨셉

1. 숫자 오름차순 정렬

2. 숫자 몇개씩 묶음

3. 묶은 뭉텅이 내부에서 양자화

 

 

초안

내코드 ( 정답, 4ms)

/**
 * @name    8.9. 양자화
 * @ID      QUANTIZE
 * @date    2019-08-08
 * @author  Sunmon
 */

#include <iostream>
#include <algorithm>
#include <cstring>

using namespace std;
const int INF = 987654321;
int N, S;
int nums[100];
int cache[100][10+1];
int sum[100+1];     //sum[x] : num[0] ~ num[x]까지의 부분합
int sqrSum[100+1];  //sqrSum[x] : num[0]^2 ~ num[x]^2의 부분합

void saveSum()
{
    sort(nums, nums+N);

    sum[0] = nums[0];
    sqrSum[0] = nums[0] * nums[0];
    for(int i = 1; i<N; i++)
    {
        sum[i] = sum[i-1] + nums[i];
        sqrSum[i] = sqrSum[i-1] + nums[i]* nums[i];
    }
}

//nums[from]부터 size개 만큼 골랐을 때 최소 편차값 리턴
//nums[from] 포함
int minError(int from, int size)
{

    int s = sum[from+size-1] - (from == 0? 0: sum[from-1]);
    int sqr = sqrSum[from+size-1] - (from == 0? 0: sqrSum[from-1]);
    int mean = int(0.5 + (double)s/size);    //반올림

    return sqr - 2 * s * mean + mean * mean * size; 

}


//from부터 parts개로 잘랐을 때 양자화하는 최소값 리턴
int quantize(int from, int parts)
{
    //base case
    if(from == N) return 0;
    if(parts == 0) return INF;

    int& ret = cache[from][parts];
    if(ret != -1) return ret;

    ret = INF;
    for(int size = 1; size <= N-from; size++)
        ret = min(ret, quantize(from + size, parts -1) + minError(from, size));

    return ret;

}


int main()
{
    int C;
    cin >> C;
    while(C--)
    {
        memset(sum, 0, sizeof(sum));
        memset(sqrSum, 0, sizeof(sqrSum));
        memset(cache, -1, sizeof(cache));
        cin >> N >> S;
        for(int i = 0; i<N; i++) cin >> nums[i];
        saveSum();
        cout << quantize(0, S) << endl;

    }
}

 

주의

 

- sort 사용법 //<algorithm>

  sort(vector.begin(), vector.end());

  sort(vector.begin(), vector.end(), compareFunction);

  sort(vector.begin(), vector.end(), greater<int>());

 

- 반올림 편하게 하는 법

  int mean = int(0.5 + (double)sum/size);