백준 1932 정수 삼각형

문제

        7
      3   8
    8   1   0
  2   7   4   4
4   5   2   6   5

위 그림은 크기가 5인 정수 삼각형의 한 모습이다.

맨 위층 7부터 시작해서 아래에 있는 수 중 하나를 선택하여 아래층으로 내려올 때, 이제까지 선택된 수의 합이 최대가 되는 경로를 구하는 프로그램을 작성하라. 아래층에 있는 수는 현재 층에서 선택된 수의 대각선 왼쪽 또는 대각선 오른쪽에 있는 것 중에서만 선택할 수 있다.

삼각형의 크기는 1 이상 500 이하이다. 삼각형을 이루고 있는 각 수는 모두 정수이며, 범위는 0 이상 9999 이하이다.

---

코드

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

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

        //N 입력 받고 삼각형 만들기
        int n = Integer.parseInt(br.readLine());
        int[][] dp=new int[n][n];
        for(int i=0; i<n; i++){
            StringTokenizer st = new StringTokenizer(br.readLine());
            for (int j = 0; j <= i; j++)
                dp[i][j] = Integer.parseInt(st.nextToken());
        }

        //제일 아랫단부터 제일 윗단까지
        //자신과 자신의 오른쪽 중 더 큰 값을 위층에 더해준다.
        for(int i=n-1; i>0; i--)
            for(int j=0; j<i; j++)
                dp[i-1][j]+=Math.max(dp[i][j], dp[i][j+1]);

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

---

해결 과정

1. 삼각형의 아래층부터 위층까지 두 값 중 큰 값을 위 층에 더해줬다.

2. 😁