BOJ 1932 정수 삼각형 [Java]

문제

BOJ 1932 정수 삼각형

접근 방법

• 아주 쉬운 dp 문제이다.
• 위에서 부터 max 누적합을 다른 배열에 추가한다고 생각하면 된다.
• 점화식이랑 index 조건만 살피면 직관적으로 금방 풀리는 문제

구현

import java.util.*;
import java.io.*;


// 1932

class Main {
	static int n;
	static int dp[][];
	static int nums[][];
    static public void main (String [] args) throws Exception {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        StringTokenizer st;
        //StringTokenizer st = new StringTokenizer(br.readLine(), " ", false);
        
        n = Integer.parseInt(br.readLine());
        nums = new int[n][n];
        dp = new int[n][n];
        
        for (int i = 0; i < n; i++) {
        	st = new StringTokenizer(br.readLine(), " ", false);
        	
        	for (int j = 0; j <= i; j++) {
        		nums[i][j] = Integer.parseInt(st.nextToken());
        		
        		if (i == 0) {
        			dp[i][j] = nums[i][j];
        		}
        		else {
        			int bigger = 0;
        			if (j-1 < 0) bigger = dp[i-1][j];
        			else bigger = Math.max(dp[i-1][j], dp[i-1][j-1]); 
        			dp[i][j] = nums[i][j] + bigger;

        		}
        	
        	}
        }
        
        int max = -1;
        for (int i = 0; i<n;i++)
        	max = max > dp[n-1][i]? max : dp[n-1][i];
        
        System.out.println(max + "");
    }
}

제출