[백준 | Java Silver I] (#1932) 정수 삼각형

문제

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

---

접근

 

Top-down 방식을 선택해서 풀었다.

주어진 삼각형을 위와 같이 이차원 배열에 저장해줬다.그리고 아래로 한칸씩 내려가면서 숫자 합을 dp 배열에 저장했다. 

세번째 줄을 예시로 들면, 18 11 16 15 가 합이 되는데, 11과 16은 그 중에서 큰 값으로 dp 배열에 저장이 된다.

그 결과 오른쪽 사진과 같이 저장된다. 이 계산을 n-1줄(인덱스 n-2)까지 반복하면 마지막 줄에 최종적인 합들이 저장되게 된다. 그럼 그 중에서 가장 큰 값을 출력하면 가장 큰 합을 구할 수 있다. 

 

최종 코드

package week11.baek.july19.baek;

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

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

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

        //Top-down 방식으로 꼭대기에서
        // 한칸 씩(왼쪽 대각선(아래), 오른쪽 대각선(아래 오른쪽)) 내려온 합으로 dp에 저장
        int[][] dp = new int[n][n];

        dp[0][0] = triangle[0][0];
        for (int i = 0; i < n-1; i++) {
            for (int j = 0; j <=i ; j++) {
                //왼쪽 대각선(아래)
                int tmp = dp[i][j] + triangle[i+1][j];
                if(tmp > dp[i+1][j]) dp[i+1][j] = dp[i][j] + triangle[i+1][j];

                //오른쪽 대각선(아래 오른쪽)
                tmp = dp[i][j] + triangle[i+1][j+1];
                if(tmp > dp[i+1][j+1]) dp[i+1][j+1] = dp[i][j] + triangle[i+1][j+1];

            }
        }

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


        System.out.println(max);

    }
}