Algorithm/알고스팟

algospot - quantize

jhg0406 2020. 2. 3. 13:29
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
//algospot - quantize
 
#include <iostream>
#include <vector>
#include <algorithm>
using namespace std;
 
#define INF 200000000
 
int N, S;
vector<int> v;
vector<int> subv;
vector<int> subv2;
vector<vector<int>> cache;
 
void init()
{
    cin >> N >> S;
    subv2 = subv = v = vector<int>(N);
    cache = vector<vector<int>>(N, vector<int>(S+1, -1));
    for(int i = 0; i<N; ++i)
        cin >> v[i];
    sort(v.begin(), v.end());
 
    subv[0] = v[0];
    for(int i = 1; i<N; ++i)
        subv[i] = subv[i-1] + v[i];
 
    subv2[0] = v[0]*v[0];
    for(int i = 1; i<N; ++i)
        subv2[i] = subv2[i-1] + v[i]*v[i];
}
 
int getMid(int start, int end)
{
    double u = subv[end] - subv[start] + v[start];
    u /= (end-start+1);
    int v = u;
    if(u - (double)v > 0.5)
        return v + 1;
    else
        return v;
}
 
 
int mini(int start, int end)
{
    int a = getMid(start, end);
    int n = end-start + 1;
    int part = subv2[end] - subv2[start] + v[start]*v[start];
    int part2 = 2*a*(subv[end]-subv[start]+v[start]);
    int part3 = n*a*a;
    return part-part2+part3;
}
 
int dive(int from, int part)
{
    if(from == N)
        return 0;
    if(!part)
        return INF;
    int& ret = cache[from][part];
    if(ret != -1)
        return ret;
    ret = INF;
    for(int size = 0; size < N-from; ++size)
        ret = min(ret, mini(from, from+size) + dive(from+size+1, part-1));
    return ret;
}
 
int main()
{
    int C; cin >> C;
    for(int tn = 0; tn<C; ++tn)
    {
        init();
        cout << dive(0, S) << "\n";
    }
}
 cs

 

 

 

 

 

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

 

algospot.com :: QUANTIZE

Quantization 문제 정보 문제 Quantization (양자화) 과정은, 더 넓은 범위를 갖는 값들을 작은 범위를 갖는 값들로 근사해 표현함으로써 자료를 손실 압축하는 과정을 말한다. 예를 들어 16비트 JPG 파일을 4컬러 GIF 파일로 변환하는 것은 RGB 색 공간의 색들을 4컬러 중의 하나로 양자화하는 것이고, 키가 161, 164, 170, 178 인 학생 넷을 '160대 둘, 170대 둘' 이라고 축약해 표현하는 것 또한 양자화라고 할

www.algospot.com

 

 

 

 

 

QUANTIZE

DP문제

cache[from][part] : 오름차순으로 정렬된 수열에서 from부터 시작하고, 사용할수 있는 숫자가 part개 남았을때 양자화한 결과의 최소를 저장하고 있는 배열

 

 

 

 

 

시간복잡도

총 N*S개의 부분문제와 각 부분문제당 N의 시간이 걸립니다.

O(S*N^2)