BOJ 12103 짝합 수열, 7976 수열

* BOJ 12103 짝합 수열, 7976 수열

[분류 - 다이나믹  프로그래밍]

1. [패턴] 0또는 1을 요소로 길이 k를 갖는 패턴 배열을 생성해보자. 대신 합이 짝수이어야 한다. 패턴의 의미는 해당 위치가 1이면 홀수 0이면 짝수를 의미한다.

2. [규칙성] 임의의 배열을 생성했다면 마지막 요소 이후의 것을 생각해보자.

만약 길이 k를 가지는 패턴이 처음에 0으로 시작한다면 그 다음 인덱스부터 k길이가 합이 짝수이기 위해서는 다음 요소(k+1번째)는 0일 수밖에 없다. 마찬가지로 1로 시작해도 그 다음 요소는 1일 수 밖에 없다.

  결국 길이 k마다 처음에 정했던 패턴이 계속 나올 수 밖에 없고, 이 패턴 중에 주어진 배열 a를 패턴에 적용했을 때 가장 적은 비용으로 바꾸는 것을 찾으면 된다.

예시) k=5, n=12

임의로 생성된 합이 짝수인 패턴 = {1 0 0 1 0}

배열에 적용될 패턴 = {1 0 0 1 0 1 0 0 1 0 1 0}

3. [계산]

패턴에서 인덱스에 따라 개수가 0개 이상으로 등장한다. 또한 그 인덱스마다 홀수와 짝수 개수를 셈해줘야한다.

count[홀짝, 홀수면 1 짝수면 0][패턴에서의 인덱스]

->

4. [다이나믹 재귀 슈도 코드]

  패턴을 선택할 때 각 위치는 독립적이고, 누적합에 대해 홀짝 여부만이 현재 인덱스에 대해 영향을 미친다. 이렇게 k길이의 패턴을 생성했을 때 마지막에 누적합에 대한 홀짝 여부로 해당 패턴이 짝수인지 아닌질 알 수 있다.

def rec(r, p)
  if p == K
    return r == 0 ? 0 : INF
  ret = reference of dp[r][p]
  if ret != -1
    return ret
  ret = min(rec(r, p+1) + c[1][p], rec(r ^ 1, p+1) + c[0][p])
  return ret

※ 12103 문제가 7976의 확장된 문제이므로 12103 문제 소스만 올립니다.

#include<cstdio>
#include<cstring>
#include<algorithm>
using namespace std;
const int MAX_N = 1e6;
int main() {
    int n, a[MAX_N], i, j, l, r, k, dp[MAX_N][2], c[2][MAX_N] = {}, ans[MAX_N];
    scanf("%d%d", &n, &k);
    for (i = 0; i < n; i++) {
        scanf("%d", &a[i]);
        c[a[i] % 2][i % k]++;
    }
    memset(dp, 0x3F, sizeof dp);
    dp[0][0] = c[1][0];
    dp[0][1] = c[0][0];
    for (i = 1; i < k; i++) {
        for (j = 0; j < 2; j++) for (r = 0; r < 2; r++)
            dp[i][j ^ r] = min(dp[i][j ^ r], dp[i - 1][r] + c[!j][i]);
    }
    printf("%d\n", dp[k - 1][0]);
    r = 0;
    for (i = k - 1; i; i--) {
        for (j = 0; j < 2; j++) {
            l = r ^ j;
            if (dp[i][r] == dp[i - 1][l] + c[!j][i]) {
                ans[i] = j;
                r = l;
                break;
            }
        }
    }
    ans[0] = r;

    for (i = 0; i < n; i++)
        printf("%d ", ans[i % k] % 2 != a[i] % 2 ? ans[i % k] : a[i]);
    return 0;
}