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

문제링크 : https://www.acmicpc.net/problem/22857

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

#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef pair<int, int> pii;
const int MAX = 987654321;

int N, K, arr[50001];
int dp[50001][101];

int func(int cur, int cnt)
{
    if(cur > N-1 || cnt > K) return 0; //범위 및 삭제 횟수 체크

    int result = 0;
    if(dp[cur][cnt]) return dp[cur][cnt];

    if(arr[cur]%2) result = max(result, func(cur+1, cnt+1)); //홀수 (삭제)
    else result = max(result, func(cur+1, cnt)+1); //짝수 (삭제 x)
    dp[cur][cnt] = result; //값 저장
    return dp[cur][cnt];
}

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

    cin >> N >> K;

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

    int result = 0;
    for(int i=0; i<N; i++) result = max(result, func(i, 0)); //현재 위치 기준 K번 삭제 시작

    cout << result;
    
    return 0;
}

수열의 각 위치 별로 K번 삭제를 실시하여 가장 큰 값을 찾아준다.

삭제의 경우 홀수일 떄만 하면되기에 현재 위치의 값이 짝수인지 홀수인지 체크가 필요하다.

 

먼저 홀수인 경우는 삭제 과정이 이뤄진다.

삭제를 카운팅하기 위해 재귀로 다음 값을 이어서 탐색할 때, cnt를 1 증가시켜 K 번 횟수를 넘는지 아닌지 체크한다.

마찬가지로 위치가 이동했기에 cur를 1 증가시켜 위치를 이동시키고 해당 위치가 N-1을 넘어서는지도 체크가 필요하다.

 

만약 짝수이면 삭제 과정이 불필요하다.

따라서 재귀로 다음 값을 이어서 탐색할 때 삭제 횟수를 체크하는 cnt는 증가시킬 필요가 없다.

그리고 짝수의 경우 수열의 길이가 증가하므로 재귀로 탐색한 값 + 1을 해주어야 한다.

 

이후 재귀를 통해 누적된 최종 dp 값을 반환해준다.

모든 위치에 대해 이 행위를 반복하기에 반복할 떄마다 최대값을 따로 저장해주고 저장한 최대값을 출력해주어야 한다.