(알고스팟) Quantization

<문제>
https://algospot.com/judge/problem/read/QUANTIZE

<key 포인트>
N개의 숫자를 S개의 묶음으로 묶어서 해결 할 것.
만약 첫 묶음의 크기를 x라고 한다면 이제 나머지 묶음의 크기는 n-x개의 숫자를 S-1개로 묶는다. 이때 나머지 S-1개의 묶음의 합이 최소 값이어 야한다.
구간의 오차제곱의 최소합 구하기( 한개의 숫자로 표현했을시)

예를들어 1,4,6을 4로 표현

 b

∑(A[i]-m)^2=(b-a+1)^2*m^2 -2*(∑A[i])*m+∑(A[i])^2

 a

이를 미분해서 정리하면 결국 m=(∑A[i])/(b-a+1)로 평균이 된다.

이를 일일히 구하면 O(n)시간이 들지만  O(1)에 계산 할 수도 있다.

바로 A의 부분합을 계산하면 된다.

pSum[k]=i는 0부터 k 까지의 A[i]의 합이라 할때

pSum[b]-pSum[a-1]=i가 0부터 b까지인 A[i]의 합 - i가 0부터 a-1까지인 A[i]의 합으로 나타 낼 수 있다.

오차제곱도 일일히 계산하면 오래걸린다. 

오차제곱의 합= i가 a부터 b까지 일때 (A[i]-m)^2을 더한 값으로 이는 상수인 A[i]^2의 합-

2*m*(A[i]의 합)+m^2(b-a+1)이다. 이때, 첫 인자와 두번째는 m과 관련없는 부분합으로 미리 계산해 둔다.


public class Quantization {

private static int N; //사이즈
private static int p;
private static int A[];
private static int pSum[];
private static int pSqSum[];
private static int cache[][];
private static final int INF=9999;

public static void main(String[] args) throws IOException {

// TODO Auto-generated method stub

N=9;
p=3;
//BufferedReader reader=new BufferedReader(new InputStreamReader(System.in));
pSum=new int[N];
pSqSum=new int[N];
    A=new int[]{1,744,755,4,897,902,890,6,777};

cache=new int[N][p+1];
for(int row[]:cache)
Arrays.fill(row, -1);

preCalc();

System.out.println(quantize(0,3));


}

private static void preCalc(){
Arrays.sort(A);

pSum[0]=A[0];
pSqSum[0]=A[0]*A[0];

for(int i=1;i<N;i++)
{
pSum[i]=pSum[i-1]+A[i];
pSqSum[i]=pSqSum[i-1]+(A[i]*A[i]);
}

}

private static int quantize(int from,int parts){

if(from==N)return 0;
if(parts==0)return INF;
if(cache[from][parts]!=-1)return cache[from][parts];

int ret=INF;
for(int size=1;size+from<=N;size++)
{
ret=Math.min(ret,minError(from,from+size-1)+quantize(from+size,parts-1));
}
return cache[from][parts]=ret;
}

private static int minError(int lo,int hi)
{
int sum=pSum[hi]-(lo==0?0:pSum[lo-1]);
int sqSum=pSqSum[hi]-(lo==0?0:pSqSum[lo-1]);
int m=(int) (0.5+(double)sum/(hi-lo+1));

int ret=sqSum-2*m*sum+m*m*(hi-lo+1);
return ret;

}




}