문제

길이가 $N$인 수열 $S$가 있다. 수열 $S$는 1 이상인 정수로 이루어져 있다.
수열 $S$에서 원하는 위치에 있는 수를 골라 최대 $K$번 삭제를 할 수 있다.
예를 들어, 수열 $S$가 다음과 같이 구성되어 있다고 가정하자.

수열 $S$에서 4번째에 있는 4를 지운다고 하면 아래와 같다.

수열 $S$에서 최대 $K$번 원소를 삭제한 수열에서 짝수로 이루어져 있는 연속한 부분 수열 중 가장 긴 길이를 구해보자.

입력

수열 $S$의 길이 $N$와 삭제할 수 있는 최대 횟수인 $K$가 공백으로 구분되어 주어진다.
두 번째 줄에는 수열 $S$를 구성하고 있는 $N$개의 수가 공백으로 구분되어 주어진다.

출력

수열 $S$에서 최대 $K$번 원소를 삭제한 수열에서 짝수로 이루어져 있는 연속한 부분 수열 중 가장 긴 길이를 출력한다.

제한

$1 \le N \le 50,000$ 

$1 \le K \le 100$ 

$1 \le$ 원소의 값 $\le 10^6$ 

예제 입력

8 2
1 2 3 4 5 6 7 8

예제 출력 1

3

문제 해결 과정

요즘 DP 문제를 풀고 있는데, 너무 어렵다...
지난 번에 DP를 풀었을 때는 잘 풀려서 DP를 마스터했다고 생각했는데 어림도 없다.
오늘 문제는 지난 번에 풀었던 문제랑 비슷해서 그렇게 접근해보려고 했다.
그런데 일단 주어진 K 때문에 너무 헷갈렸다.
그래서 처음에는 다음과 같이 해결했다.

N, K = map(int,input().split())

numbers = list(map(int, input().split()))
dp = [0] * N
for i in range(N) :
    if numbers[i] %2 == 0 :
        dp[i] = 1 
for i in range(N) :
    for j in range(i) :
        if dp[j] >= 1 : # 짝수
            if i - j + 1 <= K :
                dp[i] = max(dp[i], dp[j]+ 1)
                K = K - (i-j+1)
print(max(dp))

짝수면 전의 단계에서 +1을 더해서 현재의 값을 구한다. 전의 단계는 중간에 K 만큼 계산해서 한다.
하지만 이 방법도 이제 보니 틀렸다.
짝수와 짝수 사이에 홀수만 있으란 법은 없기 떄문이다.

그래서 방법을 찾았는데 일단은 dp는 2차원 배열로 만들어야한다. 최대로 사용할 수 있는 횟수가 K이기 때문에 K를 사용할 수도 안할 수도 있는 것이기 때문이다.

그리고 나서 for 문을 돌리면서 짝수인지, 홀수인지 확인을 한다.
짝수라면 전의 단계에서 +1만 한다.
홀수라면 전의 단계를 그대로 이어받는데, 대신 k가 쓰이지 않을때는 그대로 0이다. k가 쓰인다는 것은 홀수를 삭제할 수 있다는 뜻인데, 홀수에는 문제에서 요구하는 수열을 만들 수가 없다.
그리고 홀수가 나올 경우에 K가 1 이상이라면, dp[i-1][j-1]의 값을 가져온다. 홀수가 나온 거 자체로 k가 쓰인 것이기 때문이기 때문에 k가 1개 덜 쓰인 단계에서 가져와야 한다.

최종 코드(Python)

n, k = map(int, input().split())
arr = list(map(int, input().split()))
 
# 행 : arr 인덱스
# 열 : 원소 삭제 횟수
dp = [[0 for _ in range(k+1)] for _ in range(n+1)]
for i in range(1, n + 1):
    for j in range(k + 1):
        if arr[i-1] % 2 == 1: # 홀수이면
            if j > 0:
                dp[i][j] = dp[i-1][j-1] 
        else:               # 짝수이면
            dp[i][j] = dp[i-1][j] + 1
            
max_length = 0
for r in dp:
    for c in r:
        max_length = max(max_length, c)
print(max_length)

최종 코드(JavsScript)

const fs = require('fs');

// 입력 파일 경로 설정 (백준 등에서 입력받을 때 '/dev/stdin' 사용)
// 로컬 테스트할 경우 'input.txt'를 사용할 수도 있음
const readFileSyncAddress = '/dev/stdin';
// const readFileSyncAddress = 'input.txt';

// 입력을 읽어와 줄 단위로 나눈 후, 배열로 변환
const input = fs.readFileSync(readFileSyncAddress).toString().trim().split("\n");

function solution(input){
    const [n, k] = input[0].split(' ').map(Number);
    const arr = input[1].split(' ').map(Number);

    const dp = Array.from({ length: n + 1 }, () => Array(k + 1).fill(0));

    for (let i = 1; i <= n; i++) {
        for (let j = 0; j <= k; j++) {
            if (arr[i - 1] % 2 === 1) { // 홀수인 경우
                if (j > 0) {
                    dp[i][j] = dp[i - 1][j - 1];
                }
            } else { // 짝수인 경우
                dp[i][j] = dp[i - 1][j] + 1;
            }
        }
    }

    // 최대 길이 계산
    let maxLength = 0;
    for (let i = 0; i <= n; i++) {
        for (let j = 0; j <= k; j++) {
            maxLength = Math.max(maxLength, dp[i][j]);
        }
    }

    console.log(maxLength);
}

solution(input)

참고 블로그

https://zero0205.tistory.com/276

새로 알게 된 점

JavaScript

배열 만들기, 2차원 배열 만들기