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

 

문제

길이가 N인 수열 S가 있다. 수열 S 는 1 이상인 정수로 이루어져 있다.

수열 S 에서 원하는 위치에 있는 수를 골라 최대 K 번 삭제를 할 수 있다.

예를 들어, 수열 S 가 다음과 같이 구성되어 있다고 가정하자.

수열 S : 1 2 3 4 5 6 7 8

수열 S 에서 4번째에 있는 4를 지운다고 하면 아래와 같다.

수열 S : 1 2 3 5 6 7 8 

수열 S 에서 최대 K 번 원소를 삭제한 수열에서 짝수로 이루어져 있는 연속한 부분 수열 중 가장 긴 길이를 구해보자.

입력

수열 S 의 길이 N 와 삭제할 수 있는 최대 횟수인 K 가 공백으로 구분되어 주어진다.

두 번째 줄에는 수열 S 를 구성하고 있는 N 개의 수가 공백으로 구분되어 주어진다.

 

출력

수열 S 에서 최대 K 번 원소를 삭제한 수열에서 짝수로 이루어져 있는 연속한 부분 수열 중 가장 긴 길이를 출력한다.

 

접근 방식

 

투 포인터를 사용해 배열의 첫 번째 위치에 st, en 변수를 두고 en을 증가시키면서 홀수의 개수를 확인하면 된다

홀수 삭제 횟수를 cnt 변수를 사용해 저장한다.

만약 cnt 변수의 값이 K보다 크다면 st 변수가 홀수였는지 확인하고 cnt값을 감소시킨 후에 st++ 처리해준다.

만약 홀수인데 아직 K번 삭제하지 않았으면 cnt 변수를 증가시키고 최대 부분 수열의 값을 갱신시킨다

홀수이고 K번 삭제를 했다면 en++처리해주면 된다!

 

코드

 

#include<bits/stdc++.h>
using namespace std;

int N,K; 
vector<int> v;

int main() {
    ios::sync_with_stdio(false); cin.tie(0);
    cin>>N>>K;
    for(int i=0; i<N; i++) {
        int x; cin>>x;
        v.push_back(x);
    }
    
    int st = 0, en = 0, mx = 0, cnt=0;

    while(en < N) {
        if(cnt > K) {
            if(v[st] % 2 == 1) cnt--;
            st++;
        }
        else {
            if(v[en] % 2 == 1) cnt++;
            en++;
        }
        if(cnt <= K) mx = max(mx, en-st-cnt);
    }

    cout<<mx;
}