[백준 2240 : JAVA] 자두나무 / DP

문제

---

 

 

 

풀이

---

만약 자두를 먹는 위치가 두 군데가 아니라, 한 군데였다면 훨씬 쉽게 느껴졌을지도 모른다.
한 군데라면 1차원이지만, 두 군데 이상부터는 2차원이 되기 때문이다.

예제 입력을 표로 나타내보면 다음과 같다.

 

[그림 1] 예제 입력을 표로 나타냈을 때

 

현재 2초이고, 1의 위치에 있다고 하자. 얘가 이전에 있을 수 있는 위치는 두 군데다.

1. 1초에 1의 위치에 있을 경우

2. 1초에 2의 위치에 있을 경우 (이 경우 이동을 해야하기 때문에 현재 위치의 이동횟수-1 을 가진다)

DP[현재 위치][시간][이동횟수] 
DP[1][2][W] = Math.max(DP[1][1][W], DP[2][1][W - 1]) + (해당 초에 해당 위치에 자두가 떨어지면 +1, 아니면 +0)

 

그리고 위의 점화식을 반복문으로 구성하기 위해, 초기 이동횟수를 0이 아닌 1로 잡았다. 

 

 

 

코드

---

import java.io.*;
import java.util.*;

public class Main {

    private static int T, W;
    private static int[] arr;
    private static int[][][] cache; // [현재 위치][시간][이동횟수]

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

        cache = new int[3][T + 1][W + 2];

        for (int i = 1; i <= T; i++) {
            for (int j = 1; j <= W + 1; j++) {
                if (arr[i] == 1) {
                    cache[1][i][j] = Math.max(cache[1][i - 1][j], cache[2][i - 1][j - 1]) + 1;
                    cache[2][i][j] = Math.max(cache[2][i - 1][j], cache[1][i - 1][j - 1]);
                } else {
                    if (i == 1 && j == 1) continue;
                    cache[1][i][j] = Math.max(cache[1][i - 1][j], cache[2][i - 1][j - 1]);
                    cache[2][i][j] = Math.max(cache[2][i - 1][j], cache[1][i - 1][j - 1]) + 1;
                }
            }
        }

        int result = 0;
        for (int i = 1; i <= W + 1; i++) {
            result = Math.max(result, Math.max(cache[1][T][i], cache[2][T][i]));
        }

        System.out.println(result);
    }
}