DP / 백준 1932 정수 삼각형

 

문제 접근

점화식 도출

 

dp[i][j]=dp[i-1][j]+arr[i][j];

>> 맨왼쪽

 

dp[i][j]=dp[i-1][j-1]+arr[i][j]; 

>> 맨오른쪽

 

dp[i][j]=Math.max(dp[i-1][j-1], dp[i-1][j])+arr[i][j];

>> 가운데

풀이

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

public class S1932 {
    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 + 1][n + 1];
        int[][] dp = new int[n + 1][n + 1];

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

        dp[1][1] = arr[1][1];
        for (int i = 2; i <= n; i++) {
            for (int j = 1; j <= i; j++) {
                if (j == 1) {
                    dp[i][j] = dp[i - 1][j] + arr[i][j];
                    continue;
                }
                if (j == i) {
                    dp[i][j] = dp[i - 1][j - 1] + arr[i][j];
                    continue;
                }
                dp[i][j] = Math.max(dp[i - 1][j - 1], dp[i - 1][j]) + arr[i][j];
            }
        }

        int result = 0;
        for (int i = 1; i <= n; i++) {
            result = Math.max(result, dp[n][i]);
        }

        System.out.println(result);
    }
}