[백준](Java)1932 - 정수 삼각형

민지킴·2021년 8월 25일
0

백준

목록 보기
48/48
post-thumbnail

문제 링크

https://www.acmicpc.net/problem/1932

문제 풀이


코드

import java.util.*;

public class Main {


    public static void main(String[] args) {

        Scanner sc = new Scanner(System.in);

        int n = sc.nextInt();

        int [][] map = new int[n][n];
        int [][] dp = new int [n][n];
        for(int i=0; i<n; i++){
            for(int j=0; j<=i; j++){
                map[i][j] = sc.nextInt();
            }
        }
        dp[0][0] = map[0][0];
        for(int i=1; i<n; i++){
            for(int j=0; j<=i; j++){
                if(j==0){
                    dp[i][j] = map[i][j]+dp[i-1][0];
                }else if(j==i){
                    dp[i][j] = map[i][j] + dp[i-1][i-1];
                }else{
                    dp[i][j] = Math.max(map[i][j]+dp[i-1][j-1], map[i][j]+dp[i-1][j]);
                }
            }
        }

        Arrays.sort(dp[n-1]);
        System.out.println(dp[n-1][n-1]);
    }
}

profile
하루하루는 성실하게 인생 전체는 되는대로

0개의 댓글