백준 1932번 정수 삼각형 [JAVA]

 

 

알고리즘 설계

 

삼각형의 크기 5입력
=>list[5][5] (값을 입력받는 배열) 생성 
7                
38
810
2744
45265
입력안한된 구간은 0으로 알아서 초기화 된다 (이게 point)


dp[5][5]생성
dp배열 정의: dp[n][m] ->n층이고 선택한 위치가 m인 숫자인거까지의 최댓값  

dp[0][0]=list[0][0]

일단 dp[n][m]에서 m=0일떄는 한쪽에서밖에 못온다
점화식 정의: dp[i][j]=dp[i-1][j]+list[i][j]

그외에는 양쪽에서 올 수 있다 (매 행의 오른쪽 끝 숫자들 걱정할 필요없다 그 오른쪽에서 0인놈들이 기다리고 있다 )
ex)
마지막으로 선택한 숫자가 list[4][4]일때 
dp[4][4]=dp[3][4]+list[4][4]
           =dp[3][3]+list[4][4] 중에서 큰수 
마지막으로 선택한 숫가자 list[4][3]일때 
dp[4][3]=dp[3][3]+list[4][3]
           =dp[3][2]+list[4][3] 중에서 큰 수

마지막으로 선택한 숫자가 list[4][2]일때 
dp[4][2]=dp[3][2]+list[4][2] 
           =dp[3][1]+list[4][2] 중에서 큰수

점화식 정의: dp[n][m]=max(dp[n-1][m]+list[n][m], dp[n-1][m-1]+list[n][m])


dp[n-1][0]~dp[n-1][n-1] 중에서 최댓값이 n입력 됬을때 0층부터 n-1층까지 중에서 얻을수 있는 최댓값이다

 

 

import java.util.*;
public class Main {
    public static void main(String[] args){
        Scanner sc=new Scanner(System.in);
        int n=sc.nextInt();
        int[][]list=new int[n][n];
        int[][]dp=new int[n][n];

        for(int i=0;i<n;i++){
            for(int j=0;j<i+1;j++)
                list[i][j]=sc.nextInt();
        }

        dp[0][0]=list[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]+list[i][j];
                }
                else {
                    dp[i][j] = Math.max(dp[i - 1][j] + list[i][j], dp[i - 1][j - 1] + list[i][j]);
                }
            }
        }

        int max=0;
        for(int i=0;i<n;i++){
            if(dp[n-1][i]>max)
                max=dp[n-1][i];
        }

        System.out.print(max);


    }
}