백준 정수 삼각형

정수 삼각형

다이나믹 프로그래밍 문제로 점화식만 파악하면 쉽게 구현 가능함

import java.util.Scanner;

public class Main{
    
    public static void main(String[] args){
        Scanner sc = new Scanner(System.in);
        int n = sc.nextInt();
        
        int[][] nums = new int[n][n];
        
        for(int i = 0; i<n; i++) {
            for(int j = 0; j<=i; j++) {
                nums[i][j] = sc.nextInt();
            }   
        }
        int[][] dp = nums.clone();
        
        for(int i = 1; i<n; i++) {
            for(int j = 0; j<=i; j++) {
                int first = 0;
                int second = dp[i-1][j];
                
                if(j >0) {
                    first = dp[i-1][j-1];
                }
                dp[i][j] = dp[i][j] + Math.max(first,second);
                
            }   
        }
        int result = 0;
        
        for(int i = 0; i<n; i++) {
            result = Math.max(result,dp[n-1][i]);;   
        }
        System.out.println(result);
    }
    
}