AOJ - QUANTIZE

AOJ - QUANTIZE

일단 내가 처음에 푼 방법을 설명하고 좀더 책에 나온대로 최적화 하는 과정을 설명하자.

내가 푼 방법

dp[i][j][k][used] = 현재 i번 째를 보고 있고 마지막으로 양자화되는 숫자가 j이고 남은 양자화 횟수가 k이고 이 j를 한 번이라도 양자화에 썼다면 used=1 일 때, 끝까지 양자화를 진행했을 때의 $[i,\,n)$ 구간 에서의 최소값

정렬한 후에 구해주면 된다.

이 방법은 시간복잡도가 $O(2TNS \cdot Max_N)$ 이고 좀 최적화를 하면 500ms 정도로 통과된다.

const int inf = 1e9;  
int dp[101][1001][11][2];  
void solve() {  
   memset(dp, -1, sizeof dp);  
   int n, s;  
   cin >> n >> s;  
   vi a(n);  
   fv(a);  
   sort(all(a));  
   s = min(s, n);  
   function<int(int, int, int, int)> fn = [&](int i, int j, int k, int used) -> int {  
      if (j > 1000) return inf;  
      if (i == n) {  
         if (k == s) return inf;  
         return 0;  
      }  
      int &ret = dp[i][j][k][used];  
      if (~ret) return ret;  
      ret = inf;  
  
      // 현재 수로 양자화한다음 넘기기  
      if (used) {  
         ret = min(ret, (a[i] - j) * (a[i] - j) + fn(i + 1, j, k, 1));  
      } else {  
         if (k)  
            ret = min(ret, (a[i] - j) * (a[i] - j) + fn(i + 1, j, k - 1, 1));  
      }  
  
      // 양자화하는 수를 하나 증가시켜보기  
      if (k)  
         ret = min(ret, fn(i, j + 1, k, 0));  
  
      return ret;  
   };  
   cout << fn(0, a[0], s, 0) << endl;  
}

정해

이 문제는 정렬을 마치면 $S$개의 구간으로 나눌 때의 최소값을 찾는 문제이다.

각 $[L,~R]$ 구간에 대하여 $A_L \le X \le A_R$ 인 $X$ 중 $\displaystyle\sum_{i=L}^{R} \left( A_i-X \right)^2$ 가 최소값이 나오는

일단 $X$를 안다면 dp[i][k] 에서 $k=1$이여서 더 이상 구간을 나눌 수 없다면 $[i,~n-1]$ 구간에서의 $X$를 찾고 정답에 더해주고 반환해주면 끝이고,

$k \ge 2$ 라서 구간을 더 나누어줄 수 있다면 $[i,~n-k]$ 까지 모두 훑으며 지금 구간으로 정하고 현재 구간에서의 양자화된 오차 제곱의 합을 dp[다음 구간 시작][k-1] 과 더해줄 수 있다.

$X$ 를 직접 $O(N)$ 으로 찾아줘도 시간적으로 부족하진 않지만, 책에서는 미분을 하는 방법을 알려준다.

$\displaystyle\sum_{i=L}^{R} \left( A_i-X \right)^2=\sum_{i=L}^{R}(A_{i}^{2})-2\sum_{i=L}^{R}(A_i)X+(R-L+1)X^2$ 임을 본다면 이 식은 $X$ 에 대한 이차식이다.

아래로 볼록한

$\displaystyle\sum_{i=L}^{R}(A_{i}^{2})$과 $\displaystyle\sum_{i=L}^{R}(A_i)$ 는 미리 전처리를 해두면 $O(1)$에 구할 수 있기 때문에 이차식이 최소가 되는 값은 $ax^2+bx+c$ 에서 $x=-\dfrac b{2a}$ 이므로 저 식에 대입하면 $\displaystyle\sum_{i=L}^{R} \left( A_i-X \right)^2$ 를 결국 $O(1)$에 구할 수 있다는 결론이 나온다.

결론적으로 시간 복잡도는 $O(N^2S)$ 가 된다.

코드는 짜기 귀찮아서 생략한다.