백준 22857번 가장 긴 짝수 연속한 부분 수열(small) C++

출처 : https://www.acmicpc.net/problem/22857

포인터 두개 (start, end)를 이용해서 탐색을 하는데, start 인덱스의 원소가 짝수일 때만 검사하고, 홀수가 k+1 들어가있는 가장 작은 수열을 찾는다.

ex) 수열 S가 1, 2, 3, 4, 5, 6, 7, 8, 9 이고 K가 2라면 처음 찾는 수열은 2, 3, 4, 5, 6, 7 일 것이다. 이 수열에서 짝수로만 이루어져있는 수열은 2, 4, 6 이고 길이는 end - start - (cnt - 1)로 구할 수 있다. cnt는 찾은 홀수의 개수이고 1을 cnt에서 빼주는 이유는 홀수를 k개가 아닌 k+1개를 찾았기 때문에 더 찾은 1개를 cnt에서 빼주는 것이다.

 

그리고 찾은 수열을 일단 유지하면서 start를 이동시키고 start 인덱스의 원소가 홀수면 cnt를 줄여준다. 

 

두번째 경우는 start 인덱스의 원소가 홀수이기 때문에 cnt만 1 줄여주고 다음으로 넘어갔다.

그리고 인덱스가 배열의 크기를 넘어가는 경우도 고려해야 한다.

 

#include <iostream>
#include <string>
#include <vector>
#include <math.h>
#include <algorithm>
#include <utility>
#include <stack>
#include <queue>
#include <math.h>
#include <set>
#include <map>
#include <unordered_map>
#include <unordered_set>
#include <iomanip>

using namespace std;
using ll = long long;

int main() {
	ios_base::sync_with_stdio(false);
	cin.tie(NULL);
	cout.tie(NULL);

	int n, k;
	cin >> n >> k;
	vector<int> v(n);
	for (int i = 0; i < n; i++) {
		cin >> v[i];
	}
	int ans = 0;
	int start = 0;
	int cnt = 0;
	int end = start;
	while (start < n) {
		if (v[start] % 2 != 0) {
			if (cnt > 0) cnt--;
			start++;
			continue;
		}
		if (start >= end) {
			end = start;
			cnt = 0;
		}
		while (cnt <= k) {
			end++;
			if (end >= n) break;
			if (v[end] % 2 != 0) {
				cnt++;
			}
		}
		if (end >= n) end = n - 1;
		ans = max(ans, end - start - cnt + 1);
		start++;
	}
	cout << ans;
};