[CH08] QUANTIZE

[wbluke]

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

APSS_p244

[wbluke]

[My Point]

• 단순한 DP적용으로는 접근할 수 없는 문제. 어떤 Idea가 필요할 것 같다.

[Idea Point]

• 답의 형태 제한하기 : 주어진 수열을 정렬하면, 같은 숫자로 양자화되는 숫자들은 항상 인접해있다! => 적절한 분할 문제로 변경. DP적용 가능.
• 해당 구간에서의 최소 오차 제곱의 합 : 상식적으로 평균(반올림)으로 접근하면 최솟값. 다만 평균을 구할 때 O(n)의 시간 방법 말고도 부분합을 이용하는 상수 시간 방법이 존재한다.

[wbluke]

풀었지만 5%정도 찝찝하게 이해가 안되는 문제. 나중에 아티클 쓰면서 다시 한번 차근차근 봐야겠다.

[New Things]

• 이차원 배열의 초기화 for(int[] arr : qt.cache){ Arrays.fill(arr, -1); }