[BOJ] 1932 정수 삼각형 (Java)

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

 

<아이디어>

아래층으로 내려갈 땐 지금 당장 값이 작아도 끝까지 도착했을 때의 값이 더 클 수 있다.

그럼 반대로 생각해보면 된다!

위층으로 올라갈 때 직전 값 중 큰 값을 누적해가면 dp[0][0]이 최댓값이 된다.

for(int i=n-1; i>=0; i--){
            for(int j=0; j<n; j++){
            	// 아래층서부터의 누적값 중 최댓값인 값 (대각선 좌 / 우) 선택
                dp[i][j] = arr[i][j] + Math.max(dp[i+1][j], dp[i+1][j+1]);
            }
        }

 

<제출코드>

package BOJ.DP;

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.StringTokenizer;

public class BOJ_1932_정수삼각형 {

    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        StringTokenizer st;
        int n = Integer.parseInt(br.readLine());

        int[][] arr = new int[n][n];
        for(int i=0; i<n; i++){
            st = new StringTokenizer(br.readLine());
            for(int j=0; j<=i; j++){
                arr[i][j] = Integer.parseInt(st.nextToken());
            }
        }

        int[][] dp = new int[n+1][n+1];
        for(int i=n-1; i>=0; i--){
            for(int j=0; j<n; j++){
                dp[i][j] = arr[i][j] + Math.max(dp[i+1][j], dp[i+1][j+1]);
            }
        }

        System.out.println(dp[0][0]);
    }
}