백준 7976 수열 c++ (dp)

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

7976번: 수열

문제

정수 수열 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) 를 뜻한다.

출력

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

알고리즘 분류

• 다이나믹 프로그래밍

 

풀이

문제를 푼 사람이 적은 문제는 굉장히 스트레스 받는다.

질문도 별로 없고, 구글링해도 풀이가 없는 경우가 대부분이기 때문이다.

본인은 5퍼센트에서 계속 틀려서 고생하다가 문제를 번역한 사람의 풀이를 보고 코드를 짜냈다.

https://github.com/koosaga/iamcoder/blob/master/tests/2016_mockicpc/solution/document.pdf

 

코드는 짧지만 풀이를 이해하기 어려운 문제라 주어진 입력으로 자세한 풀이를 남긴다.

 

입력이 100만이기 때문에 웬만한 풀이론 안 되고, 규칙을 찾아 dp로 해결해야 O(N)의 시간 복잡도로 풀 수 있다.

우선 주어진 수에서 필요한 정보는 해당 수가 홀수인지 짝수인지이다.

따라서 1 2 3 4 5 6 7 8의 입력에서 해당 수가 홀/짝인지를 배열에 저장하자.

위의 예에서 주어진 수의 홀 짝 여부는 다음과 같다.

arr = {1,0,1,0,1,0,1,0}

 

이제 규칙을 찾아보자.

만약 k가 3이고, i가 0일 땐,

arr[0] + arr[1] + arr[2] ==짝을 만족해야 한다.

k가 3이고, i가 1일 땐,

arr[1] + arr[2] + arr[3] ==짝을 만족해야 한다.

k가 3이고, i가 2일 땐,

arr[2] + arr[3] + arr[4] ==짝을 만족해야 한다.

 

여기서 어떤 규칙을 찾을 수 있을까?

 

arr[0]이 1(홀)이고 arr[1]이 0(짝)이고 arr[2]가 1(홀)이기 때문에 모두 더하면 짝이다.

그다음, arr[1] + arr[2] + arr[3]이 짝이려면, 

arr[1]은 0이고 arr[2]는 1이기 때문에 arr[3]은 1이어야 한다.

그다음, arr[2] + arr[3] + arr[4]이 짝이려면,

arr[2]은 1이고, arr[3]은 1이기 때문에 arr[4]은 0이어야 한다.

그다음, arr[3] + arr[4] + arr[5]이 짝이려면,

arr[3]은 1이고, arr[4]는 0이기 때문에 arr[5]은 1이어야 한다.

 

즉 arr[i]는 arr[i+k]와 같다는 규칙을 찾을 수 있다.

위의 식대로 짝/홀을 배정하여 짝합수열을 만족하는 배열의 완성된 모습은

arr={1,0,1,1,0,1,1,0}으로

k 길이의 패턴이 반복되는 것을 알 수 있다.

 

이제 위 규칙을 가지고 풀이를 완성해보자.

우선 두 개의 배열이 필요하다.

cnt[i][j] = k길이의 i번째 원소가 j(홀/짝)인 개수

dp[i][j]  = k길이의 i번째 원소까지의 합이 j(홀/짝)인 경우 원소를 바꿔야 하는 최소 횟수

 

주어진 예제로 cnt배열을 채워 넣어 보자.

//k가 3일 땐, 0번째, 1번째, 2번째가 존재한다.

input : 1 0 1 0 1 0 1 0

cnt[0][0] = 1 , cnt[0][1] = 2

 

input : 1 0 1 0 1 0 1 0

cnt[1][0] = 2 , cnt[1][1] = 1

 

input : 1 0 1 0 1 0 1 0

cnt[2][0] = 1 , cnt[2][1] = 1

 

이후 dp를 채워보자.

dp[0][0] = cnt[0][1] =2

//0번째 원소까지의 합이 짝수일 때는 cnt[0][1]을 모두 짝수로 바꿔줘야 한다.

 

dp[0][1] = cnt[0][0] =1

//0번째 원소까지의 합이 홀수일 때는 cnt[0][0]을 모두 홀수로 바꿔줘야 한다.

 

dp[1][0] = min(dp[0][1] + cnt[1][0], dp[0][0] + cnt[1][1]) =3

//1번째 원소까지의 합이 짝수일 때

//위의 식을 해석하면 다음과 같다.

dp[0][1]+ cnt[1][0] == 0번째까지의 원소의 합이 홀수인 경우 원소들을 바꾼 최소 횟수 + 1번째 원소가 짝수여서 홀수로 바꿔야 할 개수 

vs(더 작은 거)

dp[0][0] + cnt[1][1] == 0번째까지의 원소의 합이 짝수인 경우 원소들을 바꾼 최소 횟수 + 1번째 원소가 홀수여서 짝수로 바꿔야 할 개수

 

dp[1][1] = min(dp[0][1] + cnt[1][1], dp[0][0] + cnt[1][0]) = 2

//1번째 원소까지의 합이 홀수일 때

//위의 식을 해석하면 다음과 같다.

dp[0][1]+ cnt[1][1] == 0번째까지의 원소의 합이 홀수인 경우 원소들을 바꾼 최소 횟수 + 1번째 원소가 홀수여서 짝수로 바꿔야 할 개수 

vs(더 작은 거)

dp[0][0] + cnt[1][0] == 0번째까지의 원소의 합이 짝수인 경우 원소들을 바꾼 최소 횟수 + 1번째 원소가 짝수여서 홀수로 바꿔야 할 개수

 

이 문제를 풀었다면 확장 문제도 풀어보자.

2021.08.02 - [알고리즘 문제 풀이/백준] - 백준 12103 짝합 수열 c++ (dp)

 

코드

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

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

int main() {
	ios::sync_with_stdio(false);
	cin.tie(0);
	cout.tie(0);
	cin >> n >> k;
	
	for (int i = 0; i < n; i++) {
		int num;
		cin >> num;
		cnt[i%k][num & 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];

	return 0;
}