BOJ 7976 - 수열

image.png

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

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

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

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

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

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

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

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

dp[i][0]=Min{dp[i−1][0]+c[i][1]dp[i−1][1]+c[i][0] 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]=Min{dp[i−1][0]+c[i][0]dp[i−1][1]+c[i][1] dp[i][1]=\text{Min}\begin{cases} dp[i-1][0]+c[i][0] \\ dp[i-1][1]+c[i][1] \end{cases}

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

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

You may also enjoy