백준 2240. 자두나무

https://www.acmicpc.net/problem/2240

2240번: 자두나무

'''
자두가 떨어지는 시간 T초
자두의 최대 움직임 횟수 W번
두 개의 나무에서 자두가 떨어짐(지금은 1번에 있음)

자두가 받을 수 있는 자두의 최대 개수?

이동 횟수가 홀수->현재위치 2번->2번나무 떨어진거 먹을 수 있음
이동 횟수가 짝수->현재위치 1번->1번나무 떨어진거 먹을 수 있음
현재위치와 지금 떨어지는 나무가 다를 땐 먹을 수 없음
'''
import sys
input = sys.stdin.readline

T, W = map(int,input().split())
lst = [0] + [int(input()) for _ in range(T)]
dp = [[0] * (W+1) for _ in range(T+1)]

for i in range(T+1):

    # 1번 나무에 그대로 있는 경우
    if lst[i] == 1: # 1번 나무에서 자두가 떨어짐
        dp[i][0] = dp[i-1][0] + 1
    else: # 2번 나무에서 자두가 떨어짐
        dp[i][0] = dp[i-1][0]

    # 1번 이상 움직이는 경우
    for j in range(1,W+1):
        # 현재 n번 나무인데 i초에 n번 나무에서 자두가 떨어짐
        if (lst[i] == 1 and j % 2 == 0) or (lst[i] == 2 and j % 2 == 1):
            # 움직일 것인지 현재 위치에서 받을 것인지
            dp[i][j] = max(dp[i - 1][j - 1], dp[i - 1][j]) + 1
        # i초에 떨어지는 위치와 현재 위치 다름
        else:
            dp[i][j] = max(dp[i - 1][j - 1], dp[i - 1][j])
print(max(dp[T]))