백준 1932번 정수 삼각형

이 문제를 위에서 아래로 내려오면 최대값만 찾아서 풀이한다면 100% 오답이 난다. 이유는 이렇다.

7 -> 8(15) -> 1(16) -> 7(23) -> 5(28) // 정답은 30이다!

 

따라서, 우선 다음과 같이 삼각형 정수 배열을 저장하고, DP 배열을 초기화 해준다.

삼각형 배열    DP배열
               
 7 0 0 0 0     0 0 0 0 0
 3 8 0 0 0     0 0 0 0 0
 8 1 0 0 0     0 0 0 0 0
 2 7 4 4 0     0 0 0 0 0
 4 5 2 6 5     4 5 2 6 5   <-- 삼각형의 가장 아래쪽 값으로 DP를 초기화 해준다.

 

그리고 DP 배열을 위에서 부터 탐색하며 내려간다.

 

import java.util.Scanner;

public class Main {
    static int[][] arr;
    static Integer[][] dp;
    static int n;
    public static void main(String[] args) {

        Scanner in = new Scanner(System.in);

        n = in.nextInt();

        // 값 채우기
        arr = new int[n][n];
        for (int i = 0; i < n; i++) {
            for (int j = 0; j < i + 1; j++) {
                arr[i][j] = in.nextInt();
            }
        }

        // 탐색
        dp = new Integer[n][n];
        for (int i = 0; i < n; i++) {
            dp[n - 1][i] = arr[n - 1][i];
        }
        System.out.println(search(0, 0));
    }

    static int search(int i, int j) {
        if (i == n - 1) {
            return dp[i][j];
        }

        if (dp[i][j] == null) {
            dp[i][j] = Math.max(search(i + 1, j), search(i + 1, j + 1)) + arr[i][j];
        }

        return dp[i][j];
    }
}