[Python/파이썬] 백준 22857번 가장 긴 짝수 연속한 부분 수열 (small)

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

문제

길이가 $N$인 수열 $S$가 있다. 수열 $S$는 1 이상인 정수로 이루어져 있다.

수열 $S$에서 원하는 위치에 있는 수를 골라 최대 $K$번 삭제를 할 수 있다.

예를 들어, 수열 $S$가 다음과 같이 구성되어 있다고 가정하자.

수열 S : 1 2 3 4 5 6 7 8

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

수열 S : 1 2 3 5 6 7 8 

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

입력

수열 $S$의 길이 $N$와 삭제할 수 있는 최대 횟수인 $K$가 공백으로 구분되어 주어진다.

두 번째 줄에는 수열 $S$를 구성하고 있는 $N$개의 수가 공백으로 구분되어 주어진다.

출력

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

코드

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)

 

행은 엽력받은 수열 S의 인덱스, 열은 삭제한 원소의 개수 K를 나타내는 배열 dp를 만들어서 해결한다.

`dp[i][j]`에는 `S[:i]`에서 최대 `j`번 원소를 삭제했을 때 `i`번 원소까지 짝수로 이루어져 있는 연속한 부분 수열 길이를 저장한다. 이때 최대 `j`번 원소를 지운다는 것은 `j`번 이하로 원소를 지운다는 것이지 반드시 `j`번 지운다는 말이 아니다. 짝수 개수가 `j`보다 크다면 지우지 않는 것이 더 유리하기 때문이다.

 

반복문을 돌며 `dp` 값을 갱신할 것이다.

수열 `S`(코드에서는 `arr` 배열에 받은 값)의 `i-1`번째 인덱스의 값(`S[i-1]`)이

1. 홀수
   1. $j == 0$이라면 이 원소를 삭제하지 않는 것이므로 짝수 수열이 끊기게 되므로 초기값인 0을 그대로 두면 된다.
   2. $j>0$이라면 $dp[i][j] = dp[i-1][j-1]$
2. 짝수
   가능한 짝수 수열의 길이가 1 증가하므로 $dp[i][j]=dp[i-1][j]$

최종적으로 dp테이블에 저장된 값들 중 최댓값이 짝수로 이루어져 있는 연속한 부분 수열 중 가장 긴 길이이다.

 

예를 들어, 문제의 예제 1처럼 다음과 같은 입력이 들어왔다고 하자.

8 2
1 2 3 4 5 6 7 8

 

그렇다면 dp 테이블은 다음 그림과 같이 생성된다. (행과 열이 바뀌었음!!)

 

 

i = 1부터 dp 값이 갱신되는 과정을 차례대로 보면 다음과 같다.

 

 

$i=1$

$S[0]$의 값이 홀수이므로 $j>0$일 때 $dp[i][j] = dp[i-1][j-1]$인데 `dp` 테이블의 0행의 값이 모두 0이므로 1행도 모두 0이다.

 

$i=2$

$S[1]$의 값이 짝수이므로 $dp[i][j]=dp[i-1][j]$

 

 

이런 식으로 계속 해나가면 된다.

 

 

최종적으로 만들어진 dp 테이블이다. 그러므로 dp 테이블에 저장된 값들 중 최댓값인 3이 정답.