[백준] 가장 긴 짝수 연속한 부분 수열 (small) (Java)

1. 문제설명

길이가 N인 수열 S가 있고, S는 1 이상인 정수로 이루어져 있다. 수열 S에서 원하는 위치에 있는 수를 골라 최대 K번 삭제할 수 있다. 삭제를 수행 후 수열에서 짝수로 이루어져 있는 연속한 부분 수열 중 가장 긴 길이를 구하는 문제이다.

• 시간 제한: 1초
• 메모리 제한: 1024MB

 

2. 접근 방식

• `dp[i][j]`: 수열의 `i` 번째까지의 원소에서 `j` 개의 홀수를 제거했을 때의 가장 긴 짝수 부분 수열의 길이
• 만약 `s[i]`가 짝수일 경우
  이전 상태에서 `j` 개의 홀수를 제거한 것과 동일한 상태에서 현재 짝수를 추가하여 길이를 1 증가시킨다
  ⇒ `dp[i][j] = dp[i-1][j] + 1`
• 만약 `s[i]`가 홀수이고,
  • 현재 홀수를 제거 가능할 경우 (j > 0)
    이전 상태에서 `j-1`개의 홀수를 제거한 것과 동일한 상태이다.
    ⇒ `dp[i][j] = dp[i-1][j-1]`
  • 현재 홀수를 제거할 수 없는 경우 (j == 0)
    ⇒ 현재 상태를 그대로 유지

 

3. 최종 코드

import java.io.*;
import java.util.*;

public class Main {
    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        StringTokenizer st = new StringTokenizer(br.readLine());
        int n = Integer.parseInt(st.nextToken());
        int k = Integer.parseInt(st.nextToken());
        int[] s = new int[n+1];
        int[][] dp = new int[n+1][k+1];

        st = new StringTokenizer(br.readLine());
        for(int i=1; i<=n; i++) {
            s[i] = Integer.parseInt(st.nextToken());
        }

        int maxLen = 0; // 최대 길이 저장

        for (int i = 1; i <= n; i++) {
            for (int j = 0; j <= k; j++) {
                if (s[i] % 2 == 0) { // 짝수일 경우
                    // 짝수를 포함하여 길이를 증가
                    dp[i][j] = dp[i-1][j] + 1;
                } else if (j > 0) { // 홀수일 경우, 제거 가능할 때
                    dp[i][j] = dp[i-1][j-1];
                }
                maxLen = Math.max(maxLen, dp[i][j]);
            }
        }

        System.out.println(maxLen);
    }
}