[백준] 자두나무 : Java - DP

[Gold V] 자두나무 - 2240

2240번: 자두나무

문제 설명

자두는 자두를 좋아한다. 그래서 집에 자두나무를 심어두고, 여기서 열리는 자두를 먹고는 한다. 하지만 자두는 키가 작아서 자두를 따먹지는 못하고, 자두가 떨어질 때까지 기다린 다음에 떨어지는 자두를 받아서 먹고는 한다. 자두를 잡을 때에는 자두가 허공에 있을 때 잡아야 하는데, 이는 자두가 말랑말랑하여 바닥에 떨어지면 못 먹을 정도로 뭉개지기 때문이다.

매 초마다, 두 개의 나무 중 하나의 나무에서 열매가 떨어지게 된다. 만약 열매가 떨어지는 순간, 자두가 그 나무의 아래에 서 있으면 자두는 그 열매를 받아먹을 수 있다. 두 개의 나무는 그다지 멀리 떨어져 있지 않기 때문에, 자두는 하나의 나무 아래에 서 있다가 다른 나무 아래로 빠르게(1초보다 훨씬 짧은 시간에) 움직일 수 있다. 하지만 자두는 체력이 그다지 좋지 못해서 많이 움직일 수는 없다.

자두는 T(1≤T≤1,000)초 동안 떨어지게 된다. 자두는 최대 W(1≤W≤30)번만 움직이고 싶어 한다. 매 초마다 어느 나무에서 자두가 떨어질지에 대한 정보가 주어졌을 때, 자두가 받을 수 있는 자두의 개수를 구해내는 프로그램을 작성하시오. 자두는 1번 자두나무 아래에 위치해 있다고 한다.

입력

첫째 줄에 두 정수 T, W가 주어진다. 다음 T개의 줄에는 각 순간에 자두가 떨어지는 나무의 번호가 1 또는 2로 주어진다.

출력

첫째 줄에 자두가 받을 수 있는 자두의 최대 개수를 출력한다.

 

---

어떻게 풀까?

정해진 W번만 이동하면서 최대한 많은 자두를 얻어야한다. 주어지는 정보는 시간에 따른 사과에 떨어지는 나무 정보이다. DP를 이용해서 누적된 값을 구하기로 한다. 지난 주 봤던 소마 코테에 이 문제와 비슷한 문제가 나왔었다. 근데 이것보다 더 어려웠다

 

먼저 T와 W에 대해서 그래프를 그려봤다. 1초가 지났을 때 선택할 수 있는 위치는 2가지이다. 제자리에 있거나, 이동해서 다른 나무로 가는 것. 이 두 조건을 경우의 수로 생각하면서 둘 중 최댓값을 구한다.

즉 `dp[t][w]`을 선언하고 `dp[t][w]`에는 t 시간일 때 w번 이동하여 얻을 수 있는 최대 자두 개수를 저장한다. 이때 점화식은 

 

`dp[t][w] = Math.max(dp[t-1][w], dp[t-1][w-1]) + A[][t]`이다. A[][t]는 자두의 존재를 나타낸다.

 

`dp[t-1][w]`는 가만히 있었을 때 얻을 수 있는 자두의 수, `dp[t-1][w-1]`은 이동했을 때 얻을 수 있는 자두의 수 이다. 하지만 이동 정보를 알기위해서는 현재 어떤 나무에 있는지를 알고있어야 한다. 그래서 나는 나무 정보를 저장할 수 있도록 2차원이 아닌 3차원 배열을 사용했다. `dp[tree][t][w]` 로 나무를 구별했다. 그리고 현재 시간에 n 나무에 자두가 있는지 알 수 있도록 입력 값을 `A[n][t]` 배열에 저장해줬다. 만약 2시간에 1번 나무에 자두가 있다면 `A[1][2] == 1`이다. 최종 점화식은 다음과 같다.

 

• 나무 1일 때

`dp[1][t][w] = Math.max(dp[1][t-1][w], dp[2][t-1][w-1]) + A[1][t]`

 

• 나무 2일 때

`dp[2][t][w] = Math.max(dp[2][t-1][w], dp[1][t-1][w-1]) + A[2][t]``

 

점화식대로, t=0부터 T까지, w=0부터 W까지 이중 for문을 통해 dp를 채운다. w가 0일 때는 이동 여부를 고려할 필요가 없으므로, 제자리에 있을 때 얻을 수 있는 자두 개수로 갱신해준다.

`dp[0][i][0] = dp[0][i-1][0] + A[0][i]`

 

import java.lang.*;
import java.io.*;
import java.util.StringTokenizer;

class Main {

    public static BufferedWriter bw;
    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 A[][] = new int[2][T+1];
        int dp[][][] = new int [2][T+1][W+1];

        for(int i=1; i<=T; i++){
            int n = Integer.parseInt(br.readLine());
            A[n-1][i] = 1;
        }
        dp[0][1][0] = A[0][1];
        dp[1][1][1] = dp[0][1][0] + A[1][1];
        for(int i=2; i<= T; i++){
            // 이동 안했을 때 - 제자리에서 사과가 있으면 더하기
            dp[0][i][0] = dp[0][i-1][0] + A[0][i];
            dp[1][i][0] = dp[1][i-1][0] + A[1][i];
            for(int j =1; j<=W; j++){
                
                // dp[i][j]는 i시간에 j번 이동해서 얻은 자두의 수
                // 가만히 있었을 때, 이동 해서 왔을 때 중 큰 값 구하기
                dp[0][i][j] = Math.max(dp[0][i-1][j], dp[1][i-1][j-1]) + A[0][i];
                dp[1][i][j] = Math.max(dp[1][i-1][j], dp[0][i-1][j-1]) + A[1][i];
            }
        }
        int max = 0;
        for(int n : dp[0][T])
            max = Math.max(max, n);

        for(int n : dp[1][T])
            max = Math.max(max, n);
        System.out.println(max);


    }








}

 

놓친 부분

처음 t=1일 때 초기화를 잘못 해줬다. 자두의 처음위치는 1번 나무이다. 1초일 때 2번 나무로 가기 위해선 1번 이동해야 한다. 그러므로 dp[2][1][0]은 무조건 0이고, dp[2][1][1] 값을 초기화 했어야 했다.