개발 블로그

문제 링크 : https://www.acmicpc.net/problem/2240

7 2
2
1
1
2
2
1
1

6

접근 방법

처음에는 자두의 위치를 1) 그대로 있는 경우와 2) 옆 나무로 움직이는 경우 두 가지 케이스로 분류하려고 했으나, 자두의 위치 외에도 고려해야할 변수가 두개가 더 있었다. ( 현재 몇초인지(t)와 t초에 몇번째 자두나무에서 자두가 떨어지는지) 

즉 총 세개의 변수를 고려해야함을 알았는데

추가로 매 t초마다 하는 선택이 최선의 선택이 아니며, 그렇다고 모든 경우의 수를 다 조사해 볼 수는 없기 때문에 dp로 풀기로 했다. 

dp 배열 및 각 인덱스 의미는 다음과 같다. 

dp[t][w][1] : 현재 t초이며(t초 지남), t초까지 w만큼 이동했고, 그때의 자두의 현재 위치는 1일 때 -> 먹을 수 있는 자두의 최대 갯수

dp[t][w][2] : 현재 t초이며(t초 지남), t초까지 w만큼 이동했고, 그때의 자두의 현재 위치는 2일 때 -> 먹을 수 있는 자두의 최대 갯수

이제 및 [몇번째 자두나무에서 자두가 떨어지는지] 및 [자두의 이동 여부] 케이스를 분류해서 생각해보자.

각각 2가지 경우의 수가 있다. 

-> 1번째 자두나무에서 자두가 떨어지거나 or 2번째 자두나무에서 자두가 떨어지거나

-> 그대로 있거나 Or 옆 나무로 이동하거나

Case1. 1번째 자두나무에서 자두가 떨어질 때

경우 1) 현재 자두가 1번에 있을 때 : 자두 먹을 수 있음

//자두가 t초째에 1번 자두나무 아래에 있을 때 (자두 먹은 케이스)
dp[t][w][1] = Math.max(dp[t-1][w][1], dp[t-1][w-1][2])+ 1;

=> 해석 : 1초 전에, 안 움직이고(w그대로), 1번에 있을 때 (안 움직여서 1번 그대로)

          vs 1초 전에, 움직이고 (w-1), 2번에 있을 때(2번에 있었으니까 1번으로 옮긴것)

중에 최대값을 구하고, 거기에 1을 더한다. 1을 더한 이유는

1번째 자두나무에서 자두가 떨어지는 Case1. 일 때

현재 자두의 위치가 1번 나무 아래에 있는 경우1) 이기 때문이다. 

경우 2) 현재 자두가 2번에 있을 때 : 자두 못 먹음 

//자두가 t초째에 2번 자두나무 아래에 있을 때
dp[t][w][2] = Math.max(dp[t-1][w-1][1], dp[t-1][w][2]);

=> 해석 : 1초 전에, 움직이고 (w-1), 1번에 있을 때 (1번에 있었으니까 2번으로 옮긴 것)) 

          vs 1초 전에, 안 움직이고(w그대로), 2번에 있을 때(안 움직여서 2번 그대로)

중에 최대값을 구하고, 이번엔 1을 안 더한다. 안 더한 이유는

1번째 자두나무에서 자두가 떨어지는 Case1. 일 때

현재 자두의 위치가 2번 나무 아래에 있는 경우2) 이기 때문이다. 

이런 방식으로 매 시간에 따라(t가 1부터 T일때까지)

w가 1일때부터 W일때까지 dp를 채워나간다. 

그리고 마지막에 모든 w에 대해서 dp[T][w][1], dp[T][w][2] 값 들 중에 최대값을 구한다. 

import java.util.*;

public class BOJ_2240_자두나무 {
    public static void main(String[] args){
        Scanner sc = new Scanner(System.in);
        int T = sc.nextInt();
        int W = sc.nextInt();
        int treeArr[] = new int[1001];
        int dp[][][] = new int[T+1][W+1][3];
        treeArr[0] = 1; //맨 처음 1번 나무에서 시작
        for(int i = 1; i<=T; i++){
            treeArr[i] = sc.nextInt();
        }

        //초기 값 셋팅
        if(treeArr[1] == 1){    //1초일 때, 첫번째 자두가 1번 나무에서 떨어질 경우(초기에 자두는 1번 나무 아래 있음)
            dp[1][0][1] = 1;    //1초일 때, 0번 움직여서, 현재 위치 그대로(1)   -> 자두 1개 먹음 (안움직이고 먹음)
            dp[1][1][2] = 0;    //1초일 때, 1번 움직여서, 현재 위치 바뀌고(2로) => 자두 0개 먹음 (움직이고 못먹음)
        }
        else{                   //1초일 때, 첫번째 자두가 2번 나무에서 떨어질 경우
            dp[1][0][1] = 0;    //1초일 때, 0번 움직이고, 현재 위치 그대로(1) -> 자두 0개 먹음 (안움직이고 못먹음)
            dp[1][1][2] = 1;    //1초일 때, 1번 움직이고, 현재 위치 바뀌고(2로) -> 자두 1개 먹음 (움직이고 먹음)

        }


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

            if(treeArr[t] == 1){    //1번 자두나무에서 자두가 떨어질 때
                //w = 0일 때 (안 움직였을 때) 현재 위치에 따른 초기 값 셋팅
                dp[t][0][1] = dp[t-1][0][1] + 1;    //현재 위치 1이면 = 0번 움직이고, 현재 위치 그대로 (안 움직이고 먹음)
                dp[t][0][2] = dp[t-1][0][2];        //현재 위치 2이면 = 0번 움직이고, 현재 위치 그대로 (안 움직이고 못 먹음)

                for(int w = 1; w<=W; w++){
                    //자두가 t초째에 1번 자두나무 아래에 있을 때 (자두 먹은 케이스)
                    dp[t][w][1] = Math.max(dp[t-1][w][1], dp[t-1][w-1][2])+ 1;
                    //자두가 t초째에 2번 자두나무 아래에 있을 때
                    dp[t][w][2] = Math.max(dp[t-1][w-1][1], dp[t-1][w][2]);
                }
            }

            else{                   //2번 자두나무에서 자두가 떨어질 때
                //w = 0일 때 (안 움직였을 때) 현재 위치에 따른 초기 값 셋팅
                dp[t][0][1] = dp[t-1][0][1];        //현재 위치 1이면 = 0번 움직이고, 현재 위치 그대로 (안 움직이고  못 먹음)
                dp[t][0][2] = dp[t-1][0][2] + 1;    //현재 위치 2이면 = 0번 움직이고, 현재 위치 그대로 (안 움직이고 먹음)



                for(int w = 1; w<=W; w++){
                    //자두가 t초째에 1번 자두나무 아래에 있을 때
                    dp[t][w][1] = Math.max(dp[t-1][w][1], dp[t-1][w-1][2]);
                    //자두가 t초째에 2번 자두나무 아래에 있을 때 (자두 먹은 케이스)
                    dp[t][w][2] = Math.max(dp[t-1][w-1][1], dp[t-1][w][2]) + 1;
                }
            }


        }

        int ans = 0;    //최대 값을 구해야 함
        for(int w = 0; w<=W; w++){
            ans = Math.max(ans, Math.max(dp[T][w][1], dp[T][w][2]));
        }
        System.out.println(ans);
    }
}