BOJ 12103 - 짝합 수열

BOJ 12103 - 짝합 수열

BOJ 7976 - 수열 의 아이디어 + 역추적 문제이다.

7976의 해설

근데 개인적으로 역추적이 상당히 어려웠다.

어쨌든 점화식은 다음과 같다.

$$ 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} $$

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

여기서 헷갈리는 부분은 두 번째가 $k$ 길이의 주기 수열의 parity를 의미하는 것이지 실제 수열에서 $i(0 \le i < k)$ 번째 에서 그 수로 모두 바꿔줬다는 의미가 아니라는 점이다.

즉, $dp[i][0]$ 이여도 $i$ 번째를 모두 $0$으로 바꿔줬는지, $1$으로 바꿔줬는지는 다른 얘기이다.

어쨌든 역추적에서 우리가 알 수 있는건 결국 $dp[k-1][0]$ 이 정답이라는 점이고, 여기서부터 역추적해나가자.

현재 Parity를 의미하는 변수 $p \coloneqq 0$ 로 시작한다.

만약 $p=0$ 이라고 하자.

$dp[i][p=0]=dp[i-1][0]+c[i][1]$ 이라면 우린 $i$ 번째 수를 모두 $0$ 으로 바꿔줬다는 의미이다.

만약 $dp[i][p=0]=dp[i-1][1]+c[i][0]$ 이라면 우린 $i$ 번째 수를 모두 $1$ 으로 바꿔줬다는 의미이다.

전자는 $i=1$ 에서 $p=0$ 이 되어야 하고 후자는 $p=1$ 이 되어야 한다.

$p=1$ 일 때도 비슷하게 한다. 이렇게 $4$가지 경우를 따지면서 역추적 해나가면 된다.

마지막에 $i=0$ 일 땐 현재 $p$ 값이 $i=0$ 일 때 어떤걸로 바꿔줬는지를 의미하므로 따로 처리하자.

이렇게 각 인덱스별로 $0 \ \text{or}\ 1$ 로 바꿔줬는지를 알면, 해당 $i+qk$ 의 정답의 수가 그거랑 Parity가 다르면 같게 바꿔서 정답을 출력해주도록 한다.

void solve() {
   int n, k;
   cin >> n >> k;
   vi a(n);
   fv(a);
   int s = 0;
   vvi cnt(k, vi(2));
   for (int i = 0; i < n; i++) cnt[i % k][a[i] % 2]++;

   vvi dp(k, vi(2, 1e9)), to(k, vi(2));

   dp[0][0] = cnt[0][1];
   dp[0][1] = cnt[0][0];

   for (int i = 1; i < k; i++) {
      dp[i][0] = min(dp[i - 1][0] + cnt[i][1], dp[i - 1][1] + cnt[i][0]);
      dp[i][1] = min(dp[i - 1][0] + cnt[i][0], dp[i - 1][1] + cnt[i][1]);
   }

   cout << dp[k - 1][0] << endl;
   vi ans(n, -1);
   for (int i = k - 1, x = to[k - 1][0], p = 0; i >= 0; i--) {
      if (i == 0) {
         for (int j = i; j < n; j += k) {
            if (a[j] % 2 == p) ans[j] = a[j];
            else ans[j] = p;
         }
      } else {
         // i번째의 parity
         int ret = 0;

         for (int j = 0; j < 2; j++) {
            if (dp[i][p] == dp[i - 1][p ^ j] + cnt[i][j ^ 1]) {
               ret = j;
               p = j ^ p;
               break;
            }
         }

         for (int j = i; j < n; j += k) {
            if (a[j] % 2 == ret) ans[j] = a[j];
            else ans[j] = ret;
         }
      }
   }

   for (int i: ans) {
      cout << i << ' ';
   }
}