1932 정수 삼각형

import java.io.IOException;
import java.io.BufferedReader;
import java.io.InputStreamReader;
import java.io.BufferedWriter;
import java.io.OutputStreamWriter;
import java.util.StringTokenizer;
public class main {
	static int[][] dp;
	static int N;
    static StringTokenizer st;
	public static void main(String[] args) throws IOException {
    	BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
    	BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));
    	
       	N = Integer.parseInt(br.readLine());
       	dp = new int[N][N];
       	
       	for(int i =1; i<=N; i++) {
       		st = new StringTokenizer(br.readLine()," ");
       		if(N==1) {
    			bw.write(st.nextToken()+"\n");
    			bw.flush();
    			bw.close();
    			return;
    		}
       		for(int j=0; j<i; j++) {
       			dp[i-1][j]=Integer.parseInt(st.nextToken());
       		}
       	}
       	
       	dp[1][0]+=dp[0][0];
       	dp[1][1]+=dp[0][0];
       	
       	for(int i =2; i<N; i++) {
       		
       		dp[i][0]+=dp[i-1][0];
       		for(int j=1; j<i; j++) {
       			dp[i][j]+=Math.max(dp[i-1][j-1],dp[i-1][j]);
       		}
       		dp[i][i] += dp[i-1][i-1];
       	}
       	
       	int max = 0;
       	for(int i=0;i<N; i++) {
       		if(dp[N-1][i]>=max) max = dp[N-1][i];
       	}
       	
   		bw.write(max+" ");
    	bw.flush();
    	bw.close();
    }
}

맨 위층 7부터 시작해서 아래에 있는 수 중 하나를 선택하여 아래층으로 내려올 때, 이 에제까지 선택된 수의 합이 최대가 되는 경로를 구하는 프로그램을 작성하라. 

아래층에 있는 수는 현재 층에서 선택된 수의 대각선 왼쪽 또는 대각선 오른쪽에 있는 것 중에서만 선택할 수 있다.

 

-> 이 말은 곧, 밑에 있는 수에 위에서 왼쪽위랑 오른쪽위중에 큰 값을 더해나가면 된다는 뜻 ~~~~