[백준 2240] 자두나무 - JAVA

BOJ Link

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

 

 

풀이 과정

dp[시간][움직인 횟수][현재 위치(1번or2번)] = 먹은 자두 개수

 

문제에서, 1≤W≤30 이므로 움직일 수 없는 경우는 존재하지 않는다.

따라서, 맨 처음 움직이고 시작한 경우(1->2)를 같이 초기화한다.

 

1번 위치에서 2번 위치로 움직일 때, 1번 이동하여 갈수도, 3번(1->2->1), 5번(1->2->1->2->1) ... 이동하여 갈 수도 있다.

이 경우 1번 움직이는 것이 최적이지만, 어차피 갱신되므로 더 많이 움직이는 경우는 신경쓰지 않는다.

 

최대 이동 가능 횟수보다 덜 움직였을 때 최적일 수 있으므로, 모든 dp 인덱스를 순회하여 최대값을 찾아 출력한다.

제출 코드

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

class Main {
    public static void main(String[] args) throws IOException {

        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[][][] dp = new int[T + 1][W + 1][2];
        int first = Integer.parseInt(br.readLine()) - 1;
        
        dp[1][0][0] = first == 0 ? 1 : 0;
        dp[1][1][1] = first == 1 ? 1 : 0;

        for (int i = 2; i <= T; i++) {
            int plum = Integer.parseInt(br.readLine()) - 1;

            dp[i][0][0] = dp[i - 1][0][0] + (plum == 0 ? 1 : 0);
            dp[i][0][1] = dp[i - 1][0][1] + (plum == 1 ? 1 : 0);

            for (int j = 1; j <= W; j++) {
                dp[i][j][0] = Math.max(dp[i - 1][j - 1][1], dp[i - 1][j][0]) + (plum == 0 ? 1 : 0);
                dp[i][j][1] = Math.max(dp[i - 1][j - 1][0], dp[i - 1][j][1]) + (plum == 1 ? 1 : 0);
            }
        }

        int ans = 0;
        for (int i = 0; i <= T; i++) {
            for (int j = 0; j <= W; j++) {
                for (int k = 0; k < 2; k++) {
                    ans = Math.max(dp[i][j][k], ans);
                }
            }
        }
        System.out.println(ans);
    }
}