백준 g5 22862 가장 긴 짝수의 연속한 부분 수열(large) c++

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

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

 

문제

길이가 N인 수열이 주어진다. 최대 K번 원하는 수를 삭제 가능하다.

짝수로 이루어져 있는 연속한 부분 수열 중 최대 길이 구하기

 

풀이

최대 K번 원하는 수를 삭제 가능 == K번까지 홀수를 봐줄 수 있다. 

로 바꾸면 https://kyj0032.tistory.com/71 이 문제와 비슷해진다. 

 

홀수의 개수를 세면서 허용 범위까지 en을 늘려가다가, 홀수의 개수가 K를 넘으면 st++하면서 범위를 줄여나간다.

 

수도 코드

while // en번째를 추가할 차례
	if en번째 수 == 홀수
    	홀수cnt++
    while cnt[en번째 수] > K
        st++ 하면서 범위 줄이기
    
   	length = en-st+1 - 홀수cnt
    answer = max(length, answer)
    
    en++

이전 문제(https://kyj0032.tistory.com/71)와 다른 점은 홀수 일때만 cnt를 센다는 점과, length를 구할 때 홀수 cnt를 빼줘야 한다.

 

전체 코드

/*boj g5 22862 가장 긴 짝수 연속한 부분 수열 (large)*/
#include <iostream>
#define MAXN 1000005
using namespace std;

int N, K;
int a[MAXN];
int main(void) {
    ios::sync_with_stdio(0);
    cin.tie(0);
    cin >> N >> K;
    for (int i = 0; i < N; i++)
        cin >> a[i];
    int st = 0;
    int en = 0;
    int len = 0;
    int ans = 0;

    int oddCnt = 0;

    while (st < N && en < N) {
        if (a[en] % 2 == 1) {
            oddCnt++;
        }

        while (oddCnt > K) {
            if (a[st] % 2 == 1) oddCnt--;
            st++;
        }

        len = en - st + 1 - oddCnt;
        ans = max(ans, len);

        en++;
    }

    cout << ans << "\n";
}