백준 12103 짝합 수열 c++ (dp)

문제 출처 : https://www.acmicpc.net/problem/12103

12103번: 짝합 수열

문제

정수 수열 a1, a2, ..., an이 있을 때, 1 ≤ i ≤ n − k + 1 인 모든 정수 i에 대해서, ai + ai+1 + ... + ai+k−1 이 짝수라면, 이 수열을 k-짝합 수열이라고 정의한다.

당신은 수열에 있는 몇 개의 원소를 원하는 정수로 바꿀 수 있다. 최소 몇 개의 원소를 바꿔야지 수열을 k-짝합 수열로 만들 수 있는가?

입력

첫 번째 줄에는 정수 n, k가 주어진다. (1 ≤ k ≤ n ≤ 10^6)

두 번째 줄에는 n개의 정수가 주어진다. 이 중 i 번째 정수는 ai(0 ≤ ai ≤ 10^9) 를 뜻한다.

출력

첫째 줄에 바꿔야 하는 원소의 최소 개수를 출력한다.

둘째 줄에는 어떻게 원소를 바꿔야하는지 출력한다. 바뀐 정수는 (0 ≤ ai ≤ 2×10^9) 을 만족해야 한다.

알고리즘 분류

• 다이나믹 프로그래밍

풀이

이전에 풀었던 백준 7976번 수열 문제의 확장 문제로 이 문제를 풀기 전에 먼저 풀기 바란다.

2021.08.01 - [알고리즘 문제 풀이/백준] - 백준 7976 수열 c++ (dp)

 

dp를 이용해 원소를 변환하는 최소 개수는 구했다.

이제 이 dp를 이용해 원소가 바뀐 곳의 위치를 result배열에 저장해보자.

dp[i][0] = min(dp[i - 1][1] + cnt[i][0], dp[i - 1][0] + cnt[i][1]);

위의 식에서,

dp[i][0] == dp[i - 1][1] + cnt[i][0] 이라면

i번째 원소는 짝수를 홀수로 바꿨기 때문에 홀수이다.

dp[i][0] == dp[i - 1][0] + cnt[i][1] 이라면

i번째 원소는 홀수를 짝수로 바꿨기 때문에 짝수이다.

 

dp[i][1] = min(dp[i - 1][1] + cnt[i][1], dp[i - 1][0] + cnt[i][0]);

위의 식에선,

dp[i][1] == dp[i - 1][1] + cnt[i][1] 이라면

i번째 원소는 홀수를 짝수로 바꿨기 때문에 짝수이다.

dp[i][1] == dp[i - 1][0] + cnt[i][0] 이라면

i번째 원소는 짝수를 홀수로 바꿨기 때문에 홀수이다.

 

이를 이용해, k-1부터 0까지의 홀/짝 여부를 알 수 있고,

처음 입력받은 수와 홀/짝 여부가 같으면 그대로 출력, 홀/짝 여부가 다르면 바뀐 홀/짝을 출력한다. 

코드

#include <iostream>
#include <algorithm>
#define MAX 1000000
using namespace std;
int n, k;

int dp[MAX][2], cnt[MAX][2],result[MAX], arr[MAX];

int main() {
	ios::sync_with_stdio(false);
	cin.tie(0);
	cout.tie(0);
	cin >> n >> k;
	
	//비트 연산자 &(AND)
	for (int i = 0; i < n; i++) {
		int num;
		cin >> arr[i];
		cnt[i%k][arr[i] & 1]++;
	}
	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][1] + cnt[i][0], dp[i - 1][0] + cnt[i][1]);
		dp[i][1] = min(dp[i - 1][1] + cnt[i][1], dp[i - 1][0] + cnt[i][0]);
		
	}
	cout << dp[k - 1][0]<<'\n';


	//논리 연산자 !(NOT)
	//비트 연산자 ^(XOR)
	int r = 0;
	for (int i = k - 1; i > 0; i--) {
		for (int j = 0; j < 2; j++) {
			int l = r ^ j;
			if (dp[i][r] == dp[i - 1][l] + cnt[i][!j]) {
				result[i] = j;
				r = l;
				break;
			}
		}
	}
	result[0] = r;

	for (int i = 0; i < n; i++) {
		if (result[i%k] % 2 == arr[i] % 2)
			cout << arr[i] << ' ';
		else
			cout << result[i%k] << ' ';
	
	}

	return 0;
}