BOJ(백준) 7976번 수열

https://www.acmicpc.net/problem/7976

문제를 잘 읽어보면 결국 길이가 k인 모든 구간에서 홀수의 개수가 짝수인 것과 문제가 요구하는 조건이 같다는 것을 알 수 있다.

또한 i ~ i+k-1 구간의 합이 짝수일 때 i+1 ~ i+k 구간의 합도 짝수이려면 i와 i+k는 둘 다 짝수이거나 둘 다 홀수여야된다. 즉, 각 항이 홀수인지 짝수인지가 길이가 K인 사이클을 이루어 반복되어야한다.

이 두 가지를 조합하여 그리디하게 문제를 해결하는 것이 가능하다.

① 사이클에서 같은 위치에 해당하는 숫자들(예를 들어 인덱스가 1, 1+k, 1+2*k…인 값들)을 묶어서 짝수와 홀수의 개수를 세어 배열에 기록한다.
② 배열을 짝수의 개수와 홀수의 개수의 차이가 큰 순서대로 정렬한다.
③ 배열의 앞에서부터 짝수와 홀수의 개수 중 더 적은 것을 정답에 더한다(짝수의 개수가 더 적으면 전부 홀수로 통일하고 홀수의 개수가 적으면 반대로). 동시에 짝수의 개수를 더한 횟수(=홀수로 통일시킨 횟수)를 카운트한다.
④ 단, 마지막에는 카운트한 값이 홀수라면 정답에 짝수를 더하고 그렇지 않다면 홀수를 더한다.

AC code

#include <bits/stdc++.h>
using namespace std;
int t,N,K,sol,cnt;
vector<vector<int>> v;

bool cmp(vector<int> &a,vector<int> &b) {
	return abs(a[0]-a[1])>abs(b[0]-b[1]);
}

int main() {
	ios::sync_with_stdio(0);
	cin.tie(0);
	cout.tie(0);
	cin>>N>>K;
	v.resize(K,vector<int>(2));
	for(int i=0;i<N;i++) {
		cin>>t;
		if(t%2) v[i%K][1]++;
		else v[i%K][0]++;
	}
	sort(v.begin(),v.end(),cmp);
	for(int i=0;i<K-1;i++) {
		if(v[i][1]<v[i][0]) sol+=v[i][1];	
		else {
			sol+=v[i][0];
			cnt++;
		}
	}
	if(cnt%2) sol+=v[K-1][0];
	else sol+=v[K-1][1];
	cout<<sol;
}

사실 dp로 푸는 것도 가능한데 구글에 검색해보니 dp를 이용한 풀이만 나와있기도 하고 내가 처음으로 풀었던 방식이 그리디였어서 여기에서는 그리디로 문제를 푸는 방식을 설명했다.