[C++] 알고스팟/동적계획법 - Quantization

문제 링크

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

algospot.com :: QUANTIZE

 

양자값과의 오차의 제곱을 구할 때 숫자마다 하나씩 양자값을 구하고 오차를 계산하는 것이 아닌

정렬된 숫자들을 적절하게 그룹으로 묶어서 각 그룹을 한 숫자로 표현해서 값을 찾아냅니다.

 

s개의 자연수를 사용해 양자화를 해야 하는데 숫자가 낮은 값에 낮은 s를 사용하고 높은 수에 비교적 더 높은 s를 사용해야 오차를 줄일 수 있습니다. 수열을 정렬하면 같은 s로 양자화되는 수가 인접해지므로 수를 정렬해줍니다.

 

그리고 정렬된 수열을 s가지 만큼의 그룹으로 묶어 값을 표현한 다음 각 그룹에서 나온 양자값과 그룹의 오차제곱을 구하고 모든 그룹에서 구한 오차의 합을 구해주면 됩니다.

 

 

구현 코드