(Java) 백준 1932 - 정수 삼각형

문제의 그림부터 DP 문제라고 알려주고 있었다.

꽤나 많은 문제들을 풀면서 이제 문제를 보면

어떤 유형인지 대충 어떻게 설계를 해야 하는지는 알 수 있다.

다만 실제로 구현하는것은 아직도 조금 힘들다.

 

입력값을 배열로 만들고 마지막 배열의 값을 dp 배열에 복사하는 것이 첫 번째이다.

그리고 정점의 노드부터 재귀를 통해 내려온다.

마지막 노드에 도착하면 왼쪽과 오른쪽의 값 중 큰 값을 선택하고 배열의 값과 더해 dp의 값이 된다.

이런 식으로 모든 노드를 순회하면 dp[0][0] 값이 최댓값이 되어 출력하면 된다.

---

최종 코드

import java.io.BufferedReader;
import java.io.InputStreamReader;
import java.util.StringTokenizer;

public class Main {
    static int n;
    static Integer[][] dp;
    static int[][] arr;
    public static void main(String[] args) throws Exception {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        n = Integer.parseInt(br.readLine());

        // 입력값 배열에 삽입
        arr = new int[n][n];
        for (int i = 0; i < n; i++) {
            StringTokenizer st = new StringTokenizer(br.readLine());
            for (int j = 0; j < i + 1; j++) {
                arr[i][j] = Integer.parseInt(st.nextToken());
            }
        }

        // dp의 값이 0일수도 있으므로 Integer로 초기화
        dp = new Integer[n][n];

        // 배열의 마지막 값 dp 배열에 복사
        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 idx, int depth) {
        // 재귀 탈출문
        if(depth == n - 1) {
            return dp[depth][idx];
        }
        // 다음 배열의 왼쪽과 오른쪽중 더 큰값을 찾아 현재 배열의 값과 더하기
        if(dp[depth][idx] == null) {
            dp[depth][idx] = Math.max(search(idx, depth + 1), search(idx + 1 , depth + 1)) + arr[depth][idx];
        }
        return dp[depth][idx];
    }
}