[백준] 2240. 자두나무

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

2240번: 자두나무

이 문제는 처음에 봤을 때는 풀이를 봐도 이해를 못했다가 다음 날 다시 차근차근 생각해보니 스스로 풀 수 있었던 문제이다. 역시 dp는 i = 0부터 하나씩 생각하면서 dp 배열을 채워나가다 보면 규칙을 발견하게 되는 거 같다.

• 1초일 때, 2초일 때, ... w초일 때까지의 최대로 획득한 자두 개수를 구해야 한다. 그런데 몇 번 움직였는지에 따라 경우가 나뉘므로 dp 배열은 2차원 배열로, dp[][] = new int[t + 1][w + 1]이 된다.
• i초에 j번 움직였을 때 얻는 자두의 개수는 "i - 1초에서 움직이지 않아서 얻는 자두 개수"와 "i - 1초에서 한 번 움직였을 때 얻는 자두 개수" 중 더 큰 값이다.
• 즉, 점화식은 다음과 같다. 
  • dp[i][j] = max((dp[i - 1][j - 1] + 현재 나무에서 얻는 자두 개수), (dp[i - 1] + dp[j] + 현재 나무에서 얻는 자두 개수))
• 현재 나무에서 얻는 자두 개수는 현재 나무가 1번 나무이냐 2번 나무이냐에 따라 달라지는데, 시작이 1번 나무이므로, 움직인 횟수가 짝수이면 1번 나무 아래에 있고, 홀수이면 2번 나무 아래에 있게 된다.

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

public class Main {

    static BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
    static StringTokenizer st;

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

        st = new StringTokenizer(br.readLine());
        int t = Integer.parseInt(st.nextToken());
        int w = Integer.parseInt(st.nextToken());
        int[][] arr = new int[t + 1][3];
        int[][] dp = new int[t + 1][w + 1];

        for (int i = 1; i <= t; i++) {
            int tree = Integer.parseInt(br.readLine());
            if (tree == 1) {
                arr[i][1] = 1;
            }
            if (tree == 2) {
                arr[i][2] = 1;
            }
        }

        // dp 배열 초기화
        dp[1][0] = arr[1][1];
        dp[1][1] = arr[1][2];

        // dp
        for (int i = 2; i <= t; i++) {
            dp[i][0] = dp[i - 1][0] + arr[i][1]; // 1번 나무에서 쭉 내려오는 경우
            for (int j = 1; j <= w; j++) {
                int now = (j % 2 == 0 ? arr[i][1] : arr[i][2]);
                dp[i][j] = Math.max(dp[i - 1][j - 1], dp[i - 1][j]) + now;
            }
        }

        // 결과 출력
        int answer = 0;
        for (int i = 0; i <= w; i++) {
            answer = Math.max(answer, dp[t][i]);
        }
        System.out.println(answer);
    }
}