링크

1932 정수 삼각형

문제

풀이

이 문제는 DP로 풀었다.
첫번째 줄을 제외하고 그냥 누적해서 더해주면 된다.
예제를 통해 자세히 보면
7
3 8
8 1 0
이라고 하면 첫번째 줄은 그대로 7, 두번째 줄은 이전줄인 7을 더해주면 된다.
그래서 두번째 줄은 10 15가 된다.
세번째 줄은 더했던 두번째 줄에 첫번째 값은 10 + 8, 두번째 값은 두번째 줄에 3과 8 둘다 더할 수 있으니 10 + 1과 15 + 1 중 큰 값인 16을 저장한다
이런식으로 쭉쭉쭉 하면 된다.

코드

import java.io.BufferedReader;
import java.io.BufferedWriter;
import java.io.InputStreamReader;
import java.io.OutputStreamWriter;
import java.util.*;

public class Main {

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

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

        for(int i=0;i<n;i++){
            String[] line = br.readLine().split(" ");

            for(int j=0;j<line.length;j++){
                arr[i][j] = Integer.parseInt(line[j]);

                if(i == 0){
                    dp[0][0] = Integer.parseInt(line[j]);
                } else{
                    if(j == 0){
                        dp[i][j] = dp[i-1][j] + Integer.parseInt(line[j]);
                    } else{
                        dp[i][j] = Math.max(dp[i-1][j] + Integer.parseInt(line[j]), dp[i-1][j-1] + Integer.parseInt(line[j]));
                    }
                }
            }
//            System.out.println(Arrays.toString(arr[i]));
//            System.out.println(Arrays.toString(dp[i]));
        }


//        for(int i=0;i<dp.length;i++) System.out.println(Arrays.toString(dp[i]));

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

        System.out.println(max);

    }


}