1932. 정수 삼각형 (자바, Java)

기본 로직은 동적 계획법 패턴과 유사하다, 단, 앞에서의 최댓값이, 최종 최댓값 경로를 보장하는 것이 아니다.

따라서, 밑 지점 (끝지점) 부터 역순으로 나가는 Top-Down 방식을 활용해야 한다.

'행별로 최대값' 을 구하는게 아니라, '(행, 열 좌표열을 가진)특정 지점에서의 최댓값을 구한뒤,

마지막 행에서 최대값을 구해주면 된다.

 

아무튼, 로직은 맞았는데 왜 틀렸냐고 한다면...

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

public class Main {

    static int[][] tri;
    static int[][] dp;


    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        int n = Integer.parseInt(br.readLine());
        tri = new int[n][n];
        dp = new int[n][n];
        StringTokenizer st;
        for (int i=0; i<n; i++) {

            st = new StringTokenizer(br.readLine(), " ");

            for (int j=0; j<=i; j++) {
                tri[i][j] = Integer.parseInt(st.nextToken());
            }
        }
        dp[0][0] = tri[0][0];
        int max = 0;
        for (int i=0; i<n; i++) {
            max = Math.max(max, dp(n-1, i));
        }
        System.out.println(max);
    }

    static int dp(int row, int col) {
        if (dp[row][col]==0) {
            if (col==0) {
                dp[row][col] = dp(row-1, col) + tri[row][col];
            }
            else if (col==row) {
                dp[row][col] = dp(row-1, col-1) + tri[row][col];
            }
            else {
                dp[row][col] = Math.max(dp(row-1, col-1), dp(row-1, col)) + tri[row][col];
            }
        }
        return dp[row][col];
    }
}

문제 조건에서 정수의 범위를 잘못 읽었다. 0~9999인데, 1 이상으로 0이 배제된 줄 알았음.

런타임 에러 (ArrayIndexOutOfBounds)가 발생했는데,

int 배열은 default값이 0이다. 따라서 메모이제이션 되있지 않는 부분을 0인지로 판별했지만,

그냥 0이 계속되어 합이 0일수도 있는것.

 

메모이제이션 배열을 int가 아닌 Integer 배열로 바꿨고, 이 Integer배열은 default가 null 이므로 제대로 식별할 수 있었다.

 

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

public class Main {

    static int[][] tri;
    static Integer[][] dp;


    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        int n = Integer.parseInt(br.readLine());
        tri = new int[n][n];
        dp = new Integer[n][n];
        StringTokenizer st;
        for (int i=0; i<n; i++) {

            st = new StringTokenizer(br.readLine(), " ");

            for (int j=0; j<=i; j++) {
                tri[i][j] = Integer.parseInt(st.nextToken());
            }
        }
        dp[0][0] = tri[0][0];
        int max = 0;
        for (int i=0; i<n; i++) {
            max = Math.max(max, dp(n-1, i));
        }
        System.out.println(max);
    }

    static int dp(int row, int col) {
        if (dp[row][col]==null) {
            if (col==0) {
                dp[row][col] = dp(row-1, col) + tri[row][col];
            }
            else if (col==row) {
                dp[row][col] = dp(row-1, col-1) + tri[row][col];
            }
            else {
                dp[row][col] = Math.max(dp(row-1, col-1), dp(row-1, col)) + tri[row][col];
            }
        }
        return dp[row][col];
    }
}