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

10984번: 내 학점을 구해줘

---

문제)

길이가 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번 원소를 삭제한 수열에서 짝수로 이루어져 있는 연속한 부분 수열 중 가장 긴 길이를 출력한다.

 

 

 

 

 

 

풀이)

 

// 22862. 가장 긴 짝수 연속한 부분 수열 (large)
 
#include <iostream>
#include <vector>
#include <algorithm>
 
using namespace std;
 
int n, k;
vector<int> vec;
int even;
int odd;
 
int main()
{
    ios_base::sync_with_stdio(false);
    cin.tie(0); cout.tie(0);
 
    cin >> n >>  k;
 
    vec.resize(n);
    for (int& i : vec) cin >> i;
 
    // 투포인터 이동
    int s = 0;
    int e = 0;
    int ans = 0;
 
    // 배열의 끝까지 반복한다.
    while (e < n)
    {
        // 만약 홀수의 개수가 k보다 작다면
        if (odd <= k)
        {
            // e번 인덱스의 있는 수를 추가한다.
            
            // 해당 수가 홀수일 경우
            if (vec[e] % 2)
            {    // 홀수 개수 추가
                odd++;
            }
            // 해당 수가 짝수일 경우
            else
            {    // 짝수 개수 추가하고
                even++;
                // 짝수의 개수 최댓값 갱신
                ans = max(ans, even);
            }
            e++;
        }
        // 홀수의 수가 k개를 넘어섰다면
        else if (odd > k)
        {
            // k개 보다 작아질때까지 s++를 해준다.
            if (vec[s] % 2)
            {
                odd--;
            }
            else
            {
                even--;
            }
            s++;
        }
    }
 
    cout << ans;
 
    return 0;
} 

---

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

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