백준 2240번 - 자두나무

문제

백준 2240번 - 자두나무

아이디어

• 자두가 몇 번 움직이느냐에 따라서 받을 수 있는 자두의 양이 달라질 수 있어 DP를 사용해 구한다.
• 처음에는 dp[t][w] 2차원 배열을 두어 t초에 w번 움직여 얻는 자두의 최대 개수라고 가정했다가 현재 자두의 위치도 최대 개수에 영향이 있어 위치를 추가한 3차원 배열을 사용했다.
• dp[t][w][p]를 t초에 w번 움직여 p 위치에서 얻는 자두의 최대 개수라고 가정한다. 그럼 p는 1 또는 2가 될 수 있다.
• 자두는 처음 1번 자두나무에 위치해 있기 때문에 1초에 떨어지는 자두의 위치에 따라 1초 초깃값 설정이 가능하다.
• 2초부터 자두가 현재 위치에서 이동하거나 이동하지 않거나에 따른 최대 개수를 계산해 dp 배열을 채운다.
• 최종적으로 dp[t][0 ~ w][1 or 2] 중 최댓값이 정답이 된다.

예상 시간 복잡도

• 예상 시간 복잡도 : O(T x W)

코드 구현

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

public class BJ_2240 {
    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[] 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][3];

        //1초 초깃값 설정
        if (tree[1] == 1) {
            dp[1][0][1] = 1;
        } else {
            dp[1][1][2] = 1;
        }

        for (int i = 2; i <= t; i++) {

            //1번 나무에서 자두가 떨어질 때
            if (tree[i] == 1) {

                dp[i][0][1] = dp[i - 1][0][1] + 1; //1번에 있으면 이전 위치에서 움직이지 않고 1개를 받을 수 있다.
                dp[i][0][2] = dp[i - 1][0][2];     //2번에 있으면 움직이지 않으면 받을 수 없다.

                //1번~w번 움직이는 동안 받는 자두 최대 개수를 구한다.
                for (int j = 1; j <= w; j++) {
                    dp[i][j][1] = Math.max(dp[i - 1][j][1], dp[i - 1][j - 1][2]) + 1;
                    dp[i][j][2] = Math.max(dp[i - 1][j][2], dp[i - 1][j - 1][1]);
                }
            }
            //2번 나무에서 자두가 떨어질 때
            else {
                dp[i][0][1] = dp[i - 1][0][1];      //1번에 있으면 움직이지 않으면 받을 수 없다.
                dp[i][0][2] = dp[i - 1][0][2] + 1;  //2번에 있으면 이전 위치에서 움직지이 않고 1개를 받을 수 있다.

                //1번~w번 움직이는 동안 받는 자두 최대 개수를 구한다.
                for (int j = 1; j <= w; j++) {
                    dp[i][j][1] = Math.max(dp[i - 1][j][1], dp[i - 1][j - 1][2]);
                    dp[i][j][2] = Math.max(dp[i - 1][j][2], dp[i - 1][j - 1][1]) + 1;
                }
            }
        }

        int max = 0;
        for (int i = 0; i <= w; i++) {
            max = Math.max(max, Math.max(dp[t][i][1], dp[t][i][2]));
        }

        System.out.print![](https://velog.velcdn.com/images/jky00914/post/a726d606-7559-492d-8f13-2a09d02fe242/image.png)
(max);
    }
}