BOJ 12103 - 짝합 수열
BOJ 7976 - 수열 의 아이디어 + 역추적 문제이다.
근데 개인적으로 역추적이 상당히 어려웠다.
어쨌든 점화식은 다음과 같다.
정답은 이다.
여기서 헷갈리는 부분은 두 번째가 길이의 주기 수열의 parity를 의미하는 것이지 실제 수열에서 번째 에서 그 수로 모두 바꿔줬다는 의미가 아니라는 점이다.
즉, 이여도 번째를 모두 으로 바꿔줬는지, 으로 바꿔줬는지는 다른 얘기이다.
어쨌든 역추적에서 우리가 알 수 있는건 결국 이 정답이라는 점이고, 여기서부터 역추적해나가자.
현재 Parity를 의미하는 변수 로 시작한다.
만약 이라고 하자.
이라면 우린 번째 수를 모두 으로 바꿔줬다는 의미이다.
만약 이라면 우린 번째 수를 모두 으로 바꿔줬다는 의미이다.
전자는 에서 이 되어야 하고 후자는 이 되어야 한다.
일 때도 비슷하게 한다. 이렇게 가지 경우를 따지면서 역추적 해나가면 된다.
마지막에 일 땐 현재 값이 일 때 어떤걸로 바꿔줬는지를 의미하므로 따로 처리하자.
이렇게 각 인덱스별로 로 바꿔줬는지를 알면, 해당 의 정답의 수가 그거랑 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 << ' ';
}
}
Comments