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

문제

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

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

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

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

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

수열 S : 1 2 3 5 6 7 8 

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

입력

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

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

출력

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

제한

•  1≤N≤50,000$1 \le N \le 50,000$ 
•  1≤K≤100$1 \le K \le 100$ 
•  1≤$1 \le$ 원소의 값 ≤106$\le 10^6$ 

예제 입력 1

8 2
1 2 3 4 5 6 7 8

예제 출력 1

3

제출 답안

• 어려웠던 문제다.
• 투포인터를 생각했었는데 dp로 푸는 방법이 더 좋아보인다.
• https://howudong.tistory.com/46
• https://velog.io/@cksl0830/BOJ-22857-%EA%B0%80%EC%9E%A5-%EA%B8%B4-%EC%A7%9D%EC%88%98-%EC%97%B0%EC%86%8D%ED%95%9C-%EB%B6%80%EB%B6%84-%EC%88%98%EC%97%B4
• 홀수인 경우에는 k-1을 하는 이유가 횟수를 차감하지 않았을 때 길이가 필요하기 때문이다.
  • 아직 횟수가 남았을 때의 수열의 길이가 필요하기 때문에 j-1을 해서 dp에 저장하는 것이다.

'''
1. 아이디어
- dp를 만든다.
- 짝수인 경우에 횟수를 증가시켜 값을 업데이트 한다.
- 홀수인 경우에는 이전 값을 가져온다.
2. 시간 복잡도
- 
3. 변수
- num []
- dp [][]
'''

import sys
input = sys.stdin.readline

n, k = map(int,input().split())
num = [0] + list(map(int ,input().split()))
dp = [[0] * (k+1)  for _ in range(n + 1)]

for i in range(1, n+1):
    num[i] %= 2
    for j in range(k+1):
        if num[i] == 0:
            dp[i][j] = dp[i-1][j] + 1
        if j != 0 and num[i]:
            dp[i][j] = dp[i-1][j-1]

result = max(i[k] for i in dp)
print(result)