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

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

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

---

가장 긴 짝수 연속한 부분 수열 (large) 문제는 투 포인터를 이용하여 해결할 수 있습니다. 

수열의 각 원소들을 시작점으로 잡았을 때, 최대 K개의 홀수를 제거하여 만들 수 있는 짝수 수열의 최대 길이를 계산하고, 이중 가장 긴 길이를 출력하면 됩니다.

 

하지만, N이 최대 1,000,000이기 때문에, O(N²) 알고리즘은 시간 초과가 발생할 수 있습니다. 

 

수열의 시작점이 st, 끝점이 en일 때, 홀수의 개수가 cnt이라면,

seq[st]가 홀수라면, 수열의 시작점이 st + 1, 끝점이 en일 때, 홀수의 개수는 cnt - 1입니다.

seq[st]가 짝수라면, 수열의 시작점이 st + 1, 끝점이 en일 때, 홀수의 개수는 cnt입니다.

(단, seq[i]는 수열의 i번째 원소)

 

이를 이용하여 O(N)에 문제를 해결할 수 있습니다. 

 

아래는 전체 코드입니다.

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

int seq[1000010];

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

    int n, k; cin >> n >> k;
    for(int i = 0; i < n; i++) cin >> seq[i];
    
    int st = 0, en = 0; // 구간의 시작점과 끝점
    int cnt = (seq[st]&1) ? 1 : 0;  // 현재 구간의 홀수 개수
    int m = 0;    // 부분 수열 중 가장 긴 길이

    while(true){
        while(en < n - 1){  // en을 이동시킬 수 있는 경우
            if(seq[en + 1]&1) { // 다음 요소가 홀수인 경우
                if(cnt < k)  cnt++; // 홀수를 삭제할 수 있는 경우, 홀수를 포함시킴
                else break; // 홀수를 삭제할 수 없는 경우, en의 이동을 멈춤
            }
            en++;   // en을 이동시킴
        }

        if(st >= n || en >= n) break;
        m = max(m, en - st + 1 - cnt);  // 부분 수열의 가장 긴 길이

        if(seq[st]&1) cnt--;    // 구간의 시작점이 홀수인 경우, 홀수의 개수를 줄임
        st++;   // 시작점을 한 칸 이동 시킴
    }
    cout << m;
}

 

아래는 문제 해결에 사용된 테스트케이스입니다.

7 4
2 4 6 8 10 12 14
-> 7

4 0
1 3 5 7
-> 0