문제 출처

1. 문제설명

  • 길이가 N인 수열에서 원하는 위치의 홀수를 K번 삭제할 수 있다.
  • 짝수로 이루어져 있는 연속한 부분 수열 중 가장 긴 길이를 구하라



2. 알고리즘 설계

  • 투 포인터를 응용해 풀 수 있다.
  • left, right를 0부터 시작한다.
  • 짝수면 정답값을 갱신해준다.
    • index 끼리 빼주고 1을 더해야 개수가 된다.
    • 여기서 k를 사용한 횟수를 빼면 짝수의 개수가 된다.
  • 아니라면, K를 1회 사용한다.
    • 만약 K를 전부 사용했으면 left를 1 올려주는데
    • left 위치의 원소가 홀수라면 K 사용횟수를 하나 뺀다.



3. 전체 코드

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

int n, k, arr[1000005];

int main(void)
{
    ios::sync_with_stdio(false);
    cin.tie(NULL);

    cin >> n >> k;
    for(int i=0; i<n; i++)
        cin >> arr[i];

    int left=0, right=0, tmp=0, ans=0;
    while(left <= right && right < n) {
        int cur = arr[right];

        if(cur % 2 != 0) {
            if(tmp < k) tmp++;
            else {
                if(arr[left++] % 2 != 0) tmp--;
                right--;
            }
        }
        else ans = max(ans, right-left+1-tmp);
        right++;
    }

    cout << ans;

    return 0;
}