[백준] 1932 정수 삼각형 - DP JAVA

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

1932번: 정수 삼각형

코드설명

DP 문제입니다.

 

문제예시로 값을 넣으면 DP값은 아래와 같습니다.

5
7
3 8
8 1 0
2 7 4 4
4 5 2 6 5


7 0 0 0 0 0 
10 15 0 0 0 0 
18 16 15 0 0 0 
20 25 20 19 0 0 
24 30 27 26 24 0


answer = 30

각 DP값이 그 전의 대각선 값들의 합 중 최대값을 구해서 계속해서 내려오면,

최대값을 구할 수 있습니다.

 

코드

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.*;
import java.util.regex.Pattern;

public class Main {
	public static int N;
	public static int answer = 0;
	public static int[][] map;
	public static int[][] dp;
    public static void main(String[] args) throws IOException{
    	BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
    	StringTokenizer st = new StringTokenizer(br.readLine());
    	
    	N = Integer.parseInt(st.nextToken());
    	map = new int[N][N];
    	dp = new int[N][N];
    	for(int i=0;i<N;i++) {
    		st = new StringTokenizer(br.readLine());
    		for(int j=0; j<i+1;j++) {
    			map[i][j] = Integer.parseInt(st.nextToken());
    		}
    	}
    	
    	dp[0][0] = map[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] + map[i][j];	
    			}
    			else if(j == i) {
    				dp[i][j] = dp[i-1][j-1] + map[i][j];
    			}else {
    				dp[i][j] = Math.max(dp[i-1][j-1], dp[i-1][j]) + map[i][j];	
    			}
    				
    		}
    		
    	}
    	
    	
    	for(int i=0;i<N;i++) {
    		answer = Math.max(dp[N-1][i], answer); 
    	}
    	System.out.println(answer);
    	
    }
}