BOJ 7976 - 수열
이문제는 어려워서 해설을 봤다.
$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];
}
Comments