[C++] 백준 22862번 가장 긴 짝수 연속한 부분 수열 (large)

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

투 포인터 문제.

투 포인터라는 점을 알 수 있다면 쉽게 풀 수 있는 문제.

나는 BaaaaaaaaaaarkingDog 님의 0x14강 - 투 포인터 문제집인 것을 알 수 있어서 바로 투 포인터로 풀었다.

 

문제 풀이

다음과 같은 조건으로 풀었다.

각 포인터인 L이 왼쪽, R이 오른쪽이라 할 때,

• 현재 R이 짝수면 R을 한 번 더 움직인다.
• 현재 R이 홀수이지만, 홀수의 삭제가 가능하다면 R을 한 번 더 움직인다.

위 두 조건에 해당하지 않으면 다음과 같은 조건으로 확인한다.

• R이 L보다 우측에 있을 경우, L을 움직인다.
  이 때, L이 홀수였다면 삭제 카운트를 1 빼준다.
• R과 L이 같은 위치에 있을 경우, 둘 다 움직여준다.

 

위 조건으로 푼다면, 풀 수 있다.

/*
* 백준 22862번 가장 긴 짝수 연속한 부분 수열 (large)
* https://www.acmicpc.net/problem/22862
* - 투 포인터
*/
#include <iostream>
#include <vector>
#include <algorithm>

using namespace std;

int main() {
	int result = 0;

	int numCnt, maxDeleteCnt;
	cin >> numCnt >> maxDeleteCnt;

	vector<int> numVec;
	int input;
	for (int i = 1; i <= numCnt; i++) {
		cin >> input;
		numVec.push_back(input);
	}

	int currentDeleteCnt = 0;
	int currentLen = 0;
	int l = 0;
	int r = 0;

	while (r < numCnt) {
		//cout << " L : " << l << " , R : " << r << "\n";
		if (numVec[r] % 2 == 0) {
			currentLen++;
			r++;
			result = max(result, currentLen - currentDeleteCnt);
		}
		else {
			if (currentDeleteCnt + 1 <= maxDeleteCnt) {
				currentDeleteCnt++;
				currentLen++;
				result = max(result, currentLen - currentDeleteCnt);
				r++;
			}
			else {
				if (r > l) {
					if (numVec[l] % 2 == 1) currentDeleteCnt--;
					l++;
					currentLen--;
				}
				else {
					l++;
					r++;
				}
			}
		}
	}

	cout << result;

	return 0;
}