[백준 / 골드5] 2240 자두나무 (Java)

DP 사용 시 변할 수 있는 값들을 생각해보자.
이 문제의 경우 경과한 시간과 움직인 횟수다.

문제 보기

사용한 것

• 경과한 시간과 움직인 횟수에 따라 최대로 획득할 수 있는 자두의 수를 구하기 위한 DP
• int[경과한 시간(초)][움직인 횟수] 인 dp

풀이 방법

• dp를 int[T + 1][W + 1] 크기로 초기화한다. (최대 T초 만큼 지나고, 최대 W 만큼 움직일 수 있음)
• 1초가 경과할 때부터 T초가 경과할 때까지 반복문을 돌린다.
• 현재 시간에 자두가 떨어질 나무의 인덱스를 treeIdx에 저장한다.
• 현재 계산할 수 있는 최대 움직인 횟수인 maxMove는 경과한 시간과 W 중 작은 값이다.
• dp[i][0](경과한 시간 동안 한 번도 움직이지 않음)은 1초 전 값에 현재 떨어지는 나무가 1이면 1 더해준다.
• dp[i][j](경과한 시간동안 j만큼 움직임)은 다음과 같이 구한다.
  • 1초 전에 j만큼 이동했을 때 최대 값, 1초 전에 j-1만큼 이동하고 현재 시간에 움직이는 최대 값 중 더 큰 값을 저장한다.
• T초 만큼 경과했을 때 0번 ~ W번 만큼 이동하여 최대의 자두를 얻은 값인 dp[T][0] ~ dp[T][W] 중 가장 큰 값을 구하여 출력한다.

코드

public class Main {

    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        String[] line = br.readLine().split(" ");
        int T = Integer.parseInt(line[0]);
        int W = Integer.parseInt(line[1]);
        int[] treeIdxArr = new int[T + 1];
        for (int i = 1; i <= T; i++) {
            treeIdxArr[i] = Integer.parseInt(br.readLine());
        }

        int[][] dp = new int[T + 1][W + 1];
        for (int i = 1; i <= T; i++) {
            int treeIdx = treeIdxArr[i];
            int maxMove = Math.min(i, W);
            dp[i][0] = dp[i - 1][0] + (treeIdx % 2);
            for (int j = 1; j <= maxMove; j++) {
                int fall = 0;
                if (treeIdx == 1 && j % 2 == 0) {
                    fall = 1;
                } else if (treeIdx == 2 && j % 2 == 1) {
                    fall = 1;
                }
                int stay = dp[i - 1][j] + fall;
                int move = dp[i - 1][j - 1] + fall;
                dp[i][j] = Math.max(stay, move);
            }
        }

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

        System.out.println(answer);
    }
}