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

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

1932번: 정수 삼각형

 

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

public class Main {
    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));

        int n = Integer.parseInt(br.readLine());
        int[][] arr = new int[n+1][n+1];
        int[][] dp = new int[n+1][n+1];

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

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

        int answer = 0;
        for(int i=1; i<=n; i++){
            answer = Math.max(answer, dp[n][i]);
        }
        System.out.println(answer);

    }
}

 

 

dp[i][j] = (i,j)까지의 합의 최댓값 

 

 

어떤 수를 구할 때 그 전에 선택된 수는 대각선 왼쪽 위이거나 대각선 오른쪽 위가 될 수 있고, 이 두 수 중 큰 값을 구해  그다음 수를 더해야만 한다.

 

그러므로 점화식은 이렇게 표현할 수 있다.

 

 

dp[i][j] = Math.max(dp[i-1][j-1], dp[i-1][j]) + arr[i][j];