DP - 백준1932 정수 삼각형

풀이
정수삼각형을 내려가면서, 각 숫자까지 더한 최댓값을 해당 칸에 저장한다. 구간 합을 구하는 것과 똑같은 전형적인 DP문제이다.
단, 주어진 대상이 삼각형이라는 것이 문제다. 하지만 크게 어렵지 않은게, 주어진 예제 입력을 보니 아이디어가 바로 떠올랐다.

이 예시 입력같은 경우, 빈칸은 0으로 채워진 5x5 2차원 배열이라고 생각할 수 있다.
그리고 정수 삼각형에서 각 [n][k]번째 숫자의 왼쪽 아래와 오른쪽 아래 숫자는 [n+1][k]와 [n+1][k+1]와 같다. 그런데 이는 위쪽의 숫자를 기준으로 생각한 것이고, dp테이블을 채워넣을 땐 아래의 숫자를 채워넣기 위해 위의 숫자를 사용해야 하므로, 아래쪽 숫자를 기준으로 생각하면 다음과 같은 점화식이 나온다.
dp[n][k] = Math.max(dp[n-1][k] or dp[n-1][k-1]) + arr[n][k];
그리고 추가로 주의해야 할 점은 아래 코드의 주석 내용과 같다.

import java.io.*;
import java.util.*;
public class Backjoon1932 {
    public static void main(String[] args) throws IOException{
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        int n = Integer.parseInt(br.readLine());
        int[][] arr = new int[n][n+1];
        int[][] dp = new int[n][n+1];
        //arr[][]에 입력 받기
        //삼각형이지만 결국 2차원배열에 저장해야함
        //저장할 때 반복문의 각 i번째에서
        //주어진 수를 StringTokenizer로 쪼개서 채워넣는데, 쪼개서 나온 token 갯수가 배열의 길이보다 작을 수 있므로 에러 발생가능
        //-> 주어진 수를 StringTokenizer에 넣기전에 , 주어진 수에 " " + 0을 안 모자랄 만큼 더하기 
        for(int i = 0; i < n; i++){
            StringBuilder sb = new StringBuilder(br.readLine());
            //StringTokenizer에 넣기 전에, " " + 0 충분히 더하기
            for(int j = 0; j < n; j++){
                sb.append(" " + 0);
            }
            StringTokenizer st = new StringTokenizer(sb.toString());
            for(int j = 0; j < n; j++){
                arr[i][j] = Integer.parseInt(st.nextToken());
            }
        }
        //점화식
        //dp[n][k] = Math.max(dp[n-1][k] or dp[n-1][k-1]) + arr[n][k];
        //초기값 설정
        dp[0][0] = arr[0][0];
        //테이블 채우기
        for(int i = 1; i < n; i++){
            for(int j = 0; j < n; j++){
                if(j == 0){
                    dp[i][j] = dp[i-1][j] + arr[i][j];
                }else{
                    dp[i][j] = Math.max(dp[i-1][j], dp[i-1][j-1]) + arr[i][j];
                }
            }
        }
        //정수 삼각형 밑변에서 최댓값 찾기
        int answer = 0;
        for(int i = 0; i < n; i++){
            if(answer < dp[n-1][i]){
                answer = dp[n-1][i];
            }
        }
        System.out.println(answer);
    }
}