백준 1932번 정수 삼각형(JAVA)

문제

1932번: 정수 삼각형

 

풀이

import java.io.*;
import java.util.*;

public class Main {
    private static int n;
    private static int[][] dp;
    private static int[][] arr;

    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        StringTokenizer st;

        n = Integer.parseInt(br.readLine());

        arr = new int[n][n];
        dp = new int[n][n];

        for (int i = 0; i < n; i++) {
            st = new StringTokenizer(br.readLine(), " ");
            for (int j = 0; j <= i; j++) {
                arr[i][j] = Integer.parseInt(st.nextToken());
            }
        }

        for (int[] tmp : dp) {
            Arrays.fill(tmp, -1);
        }

        // 원래 배열의 마지막 행을 복사한다.
        for (int i = 0; i < n; i++) {
            dp[n - 1][i] = arr[n - 1][i];
        }

        System.out.println(func(0, 0));
    }

    private static int func(int x, int y) {
        if (x == n - 1) {
            return dp[x][y];
        }

        if (dp[x][y] == -1) {
            dp[x][y] = Math.max(func(x + 1, y), func(x + 1, y + 1)) + arr[x][y];
        }

        return dp[x][y];
    }
}

-1(정답 위치)	-1	-1	-1	-1
-1	-1	-1	-1	-1
-1	-1	-1	-1	-1
-1	-1	-1	-1	-1
4	5	2	6	5

주어진 입출력 예제를 살펴보자. arr의 배열의 마지막 행을 복사하였으니 dp 배열의 초기 상태는 위와 같을 것이다. 아래서부터 적절한 값을 찾아 올라가니 정답의 최종 위치는 (0, 0)이 될 것이다.

-1	-1	-1	-1	-1
-1	-1	-1	-1	-1
-1	-1	-1	-1	-1
-1	-1	-1	-1	-1
4	5	2	6	5

처음 func 메서드가 실행될 때 (0, 0)은 -1이다. 따라서 (1, 0)과 (1, 1) 중 큰 값을 찾아 원래 값(arr[0][0])에 더해준다. (1, 0)과 (1, 1)도 마찬가지로 -1 이므로 -1이 아닌 값을 찾을 때까지 계속 내려간다. 회색으로 표시되어 있는 칸은 스택에 쌓인 func() 메서드가 가지고 있는 위치 인자이다. 

dp[3][i] 일 때 

-1	-1	-1	-1	-1
-1	-1	-1	-1	-1
-1	-1	-1	-1	-1
2 + Math.max(4, 5) = 7	7 + Math.max(5, 2) = 12	4 + Math.max(2, 6) = 10	4 + Math.max(6, 5) = 10	-1
4	5	2	6	5

마지막 행에 도달하게 되면 -1이 아니므로 func(4, 0), func(4, 1) ... 은 4, 5, ...를 리턴한다. 그리고 dp[3][0]은 4와 5 중 큰 값을 선택하고 arr[3][0]을 더한 값으로 바뀌게 된다. 마찬가지로 dp[3][i]는 dp[4][i]와 dp[4][i + 1] 중 큰 값을 찾아 선택한다.

dp[2][i] 일 때 

-1	-1	-1	-1	-1
-1	-1	-1	-1	-1
8 + Math.max(7, 12) = 20	1 +  Math.max(12, 10) = 13	0 +  Math.max(10, 10) = 10	-1	-1
7	12	10	10	-1
4	5	2	6	5

dp[1][i] 일 때 

-1	-1	-1	-1	-1
3 + Math.max(20, 13) = 23	8 + Math.max(13, 10) = 21	-1	-1	-1
20	13	10	-1	-1
7	12	10	10	-1
4	5	2	6	5

dp[0][i] 일 때

7 + Math.max(23, 21) = 30	-1	-1	-1	-1
23	21	-1	-1	-1
20	13	10	-1	-1
7	12	10	10	-1
4	5	2	6	5

밑에서부터 계산하고 올라와서 (0,0) 위치의 최댓값인 30이 리턴된다.