접근법

DP 배열 정의:

dp[i][j]: i초까지 j번 이동했을 때 받을 수 있는 최대 자두 개수

j의 홀짝에 따라 자두의 위치가 결정:

• j가 짝수일 때: 1번 나무 아래에 있음
• j가 홀수일 때: 2번 나무 아래에 있음

초기값 설정:

이동 없이 계속 1번 나무에 있는 경우 처리

점화식:

현재 위치와 떨어지는 자두의 나무가 같을 때: 자두를 받음
두 가지 선택 중 최대값 선택:

이전 시간에서 같은 이동 횟수의 상태에서 오는 경우
이전 시간에서 한 번 더 적게 이동한 상태에서 오는 경우

예제 DP 표:

7 2
2
1
1
2
2
1
1

dp[i][j]	j=0 (1번 나무)	j=1 (2번 나무)	j=2 (1번 나무)
i=0	0	0	0
i=1(2번)	0	1	0
i=2(1번)	1	1	2
i=3(1번)	2	1	2
i=4(2번)	2	2	2
i=5(2번)	2	3	2
i=6(1번)	3	3	4
i=7(1번)	4	3	4

코드

import java.io.BufferedReader;
import java.io.InputStreamReader;
import java.util.StringTokenizer;

public class Main {

    public static void main(String[] args) throws Exception {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        StringTokenizer st = new StringTokenizer(br.readLine());
        int T = Integer.parseInt(st.nextToken());
        int W = Integer.parseInt(st.nextToken());

        int[] tree = new int[T + 1];
        for (int i = 1; i <= T; i++) {
            tree[i] = Integer.parseInt(br.readLine());
        }

        int[][] dp = new int[T + 1][W + 1];

        for (int i = 1; i <= T; i++) {
            // 이동 없는 경우
            if (tree[i] == 1) {
                dp[i][0] = dp[i - 1][0] + 1;
            } else {
                dp[i][0] = dp[i - 1][0];
            }

            // 이동이 있는 경우
            for (int j = 1; j <= W; j++) {
                if ((tree[i] == 1 && j % 2 == 0) || (tree[i] == 2 && j % 2 == 1)) {
                    dp[i][j] = Math.max(dp[i - 1][j - 1], dp[i - 1][j]) + 1;
                } else {
                    dp[i][j] = Math.max(dp[i - 1][j - 1], dp[i - 1][j]);
                }
            }
        }

        // 마지막 시간에서 모든 이동 횟수 중 최대값 찾기
        int maxJadu = 0;
        for (int j = 0; j <= W; j++) {
            maxJadu = Math.max(maxJadu, dp[T][j]);
        }
        
        System.out.println(maxJadu);
    }
}