가장 긴 짝수 연속한 부분 수열 (small) 22857

문제

접근 방법

수열의 경우 짝수이면 이전의 값에서 이어주고 홀수이면 삭제 횟수를 사용하여 이전의 값을 이어줄 수 있다.

코드

#include <iostream>
#include <vector>
using namespace std;
int N, K, ret, num;
int main()
{
    ios::sync_with_stdio(0), cin.tie(0);
    cin >> N >> K;
    vector<vector<int>> dp(K + 1, vector<int>(N));
    cin >> num;
    dp[0][0] = !(num % 2);
    ret = max(ret, dp[0][0]);
    for (int i = 1; i < N; ++i)
    {
        cin >> num;
        if (num % 2) // 짝수인가
            for (int j = 1; j <= K; ++j)
                dp[j][i] = dp[j - 1][i - 1];
        else
            for (int j = 0; j <= K; ++j)
            {
                dp[j][i] = dp[j][i - 1] + 1;
                ret = max(ret, dp[j][i]);
            }
    }
    cout << ret;
    return 0;
}

풀이

투 포인터를 활용하면 더 짧은 시간 안에 해결될 것으로 생각된다. (K의 값에서 덜 탐색하므로)

짝수인지 아닌지의 경우를 나누고 반복문을 돌면 된다.
99%쯤에서 틀린다면 길이가 1이고 첫 번째가 2인 경우를 확인 안 한 거일 수도 있다.