[Gold 5] 22862 가장 긴 짝수 연속한 부분 수열 (large)

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

22862번: 가장 긴 짝수 연속한 부분 수열 (large)

 

이 문제는 투 포인터를 사용해서 해결할 수 있다.

 

문제에서 주어지는 최대 K 번 삭제한 짝수로만 이루어진 연속한 부분 수열이라는 뜻은 홀수가 K번 이하 존재하는 연속한 부분 수열을 찾으라는 의미이다.

 

이러한 생각을 바탕으로 예제를 접근하면 아래와 같은 결과가 나온다.

1.  1 2 3 4 5 6 7 8 이 주어지면 2 4 6 이 정답이 될 수 있다.
2. 초기 start 포인터가 가리키는 0번째 인덱스가 홀수 인 경우 1 아닌경우 0으로 counter 변수를 초기화한다.
3. end 포인터가 가리키는 인덱스의 다음 인덱스가 홀수인 경우 counter를 증가시킨다. 이때 K 개 보다 커지면 탐색 종료
4. 모든 포인터가 수열의 범위를 벗어나면 탐색 종료
5. start 포인터가 가리키는 요소가 홀수인경우 counter 감소(end 포인터가 검사한 요소를 가리킬 것이기 때문)

 

#include<iostream>

using namespace std;

int N, K;
int arr[1000001];
int result = 0;

int main() {
	ios::sync_with_stdio(false);
	cin.tie(0);
	cout.tie(0);

	cin >> N >> K;

	for (int i = 0; i < N; i++)
		cin >> arr[i];

	int start=0, end=0;
	int counter = (arr[start] %2 !=0) ? 1 : 0;
	
	while (true) {
		while (end < N - 1) {
			if (arr[end + 1] %2 != 0) {
				if (counter < K)counter++;
				else break;
			}
			end++;
		}

		if (start > N || end > N)break;
		result = max(result, end - start + 1 - counter);

		if (arr[start] %2 != 0)counter--;
		start++;
	}
	cout << result << '\n';
	return 0;
}