BOJ 7976 - 수열

image.png

이문제는 어려워서 해설을 봤다.


$a_i$ 에 대해 모두 $1 \ \text{or}\ 0$ 으로 Parity만 남기자.

$a_i=a_{i+k}$ 가 되야 한다는 점을 관찰한다.

$\displaystyle \sum_{i+1}^{i+k-1} a_i$ 의 합은 일정한데 $\displaystyle \sum_{i}^{i+k-1}a_i=\sum_{i+1}^{i+k}a_i$ 가 되야 하기 때문이다.

또한 구간의 합이 짝수가 되야 한다.

$dp[i][p]=i+qk$ 의 인덱스들이 Parity가 $p$가 되도록 하는 변경 최소 횟수라고 정의한다.

정답은 $dp[k-1][0]$ 이다.

$c[i][p]$ 를 $i+qk$ 번 째 인덱스들에서 Parity가 $p$인 것의 개수라고 하면 점화식은 다음과 같다.

$$ dp[i][0]=\text{Min}\begin{cases} dp[i-1][0]+c[i][1] \\ dp[i-1][1]+c[i][0] \end{cases} $$
$$ dp[i][1]=\text{Min}\begin{cases} dp[i-1][0]+c[i][0] \\ dp[i-1][1]+c[i][1] \end{cases} $$

왜 $c$가 반대냐면 모두 $1$로 만들어주기 위해는 $c[i][0]$ 의 개수만큼 $0$ 을 변경해줘야 하기 때문이다.

void solve() {
   int n, k;
   cin >> n >> k;
   vi a(n);
   fv(a);
   for (int &i: a)i %= 2;
   int s = 0;
   vvi dp(k, vi(2, 1e9));

   for (int i = 0; i < k; i++) {
      int sum = 0, cnt = 0;
      for (int j = i; j < n; j += k) cnt++, sum += a[j];

      int to_zero = sum;
      int to_one = cnt - sum;
      if (i == 0) {
         dp[i][0] = to_zero;
         dp[i][1] = to_one;
      } else {
         dp[i][0] = min(dp[i - 1][0] + to_zero, dp[i - 1][1] + to_one);
         dp[i][1] = min(dp[i - 1][0] + to_one, dp[i - 1][1] + to_zero);
      }
   }

   cout << dp[k - 1][0];
}

Tags:

Categories:

Updated:

Comments