[DP] [백준 / 9465] 실버 1 - 스티커 (java/자바)

문제

풀이 과정

dp[ ][1] 까지 초기화를 해줍니다. 여기까지의 초기화가 돼있어야 이 문제에서의 dp 기본 초기화를 만족하게 됩니다.

dp[ ][2]로 넘어가서 최댓값을 구해보겠습니다.

dp[0][2] = ? + 100에서
?에는 어떤값들이 들어갈 수 있는지 생각해봅니다.

우선 dp[0][2]는 왼쪽,아래쪽 스티커를 기본적으로 선택 할 수 없습니다.
? 의 후보는 50, 30, 100 이겠네요. 하지만 50은 될 수 없습니다. 왜 그럴까요?
100을 보면, 100이 되기 위해 50을 더해서 100이 됐었습니다. 따라서 100을 ? 후보로 넣으면 50을 이미 고려한 상황인 것입니다.
따라서 ?의 후보는 30, 100 으로 좁힐 수 있습니다.

30과 100 중 100이 더 크기 때문에 ? = 100이 되므로
dp[0][2] = ? + 100 = 200이 됩니다.

성공 코드

package boj.DP;

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

public class boj_9465 {
    public static void main(String[] args) throws IOException {
        BufferedReader r = new BufferedReader(new InputStreamReader(System.in));
        int loop = Integer.parseInt(r.readLine());
        for (int i = 0; i < loop; i++) {
            int n = Integer.parseInt(r.readLine());
            int[][] matrix = new int[2][n];
            int[][] dp = new int[2][n];
            for (int j = 0; j < 2; j++) {
                matrix[j] = Arrays.stream(r.readLine().split(" ")).mapToInt(Integer::parseInt).toArray();
            }

            // 초기값 설정
            dp[0][0] = matrix[0][0]; //50
            dp[1][0] = matrix[1][0]; //30

            if (n > 1) {
                dp[0][1] = matrix[1][0] + matrix[0][1]; //100
                dp[1][1] = matrix[0][0] + matrix[1][1]; //40
            }
			// dp 시작
            for (int j = 2; j < n; j++) {
                dp[0][j] = Math.max(dp[1][j-1], dp[1][j-2]) + matrix[0][j];
                dp[1][j] = Math.max(dp[0][j-1], dp[0][j-2]) + matrix[1][j];
            }
            int max = Math.max(dp[0][n-1], dp[1][n-1]);

            System.out.println(max);
        }
    }
}