문제

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

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

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

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

입력
첫째 줄에 삼각형의 크기 n(1 ≤ n ≤ 500)이 주어지고, 둘째 줄부터 n+1번째 줄까지 정수 삼각형이 주어진다.

출력
첫째 줄에 합이 최대가 되는 경로에 있는 수의 합을 출력한다.

예제 입력 1
5
7
3 8
8 1 0
2 7 4 4
4 5 2 6 5

예제 출력 1
30

---

접근

각 숫자를 선택했을 때의 최대 합을 이차원 dp 배열에 저장해 나가면 되는 문제이다. 공교롭게도 얼마전에 풀었던 1149 RGB거리와 굉장히 유사한 문제여서 어렵지 않게 푼 것 같다.

아래층에 있는 수는 현재 층에서 선택된 수의 대각선 왼쪽 또는 대각선 오른쪽 둘 중 하나만 선택할 수 있다. 그러니
i번째 층 j번째 수를 선택했을 때의 최대 합(dp[i][j])은

• 위층(i-1층)에서 대각선 왼쪽을 선택했을 때의 최대 합(dp[i - 1][j - 1])
• 위층(i-1층)에서 대각선 오른쪽을 선택했을 때의 최대 합(dp[i - 1][j])

둘 중 최댓값을 취한 후 여기에i번째 층 j번째 수를 더해준 것과 같다.

이전 층까지의 최댓값 + 현재 숫자
이걸 계속 반복해 나가는 것.

구현

import java.io.*;

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[][] dp = new int[n + 1][n + 1];

        for (int i = 1; i < n; i++) {
            String[] input = br.readLine().split(" ");
            for (int j = 1; j <= i; j++) {
                dp[i][j] = Math.max(dp[i - 1][j - 1], dp[i - 1][j]) + Integer.parseInt(input[j - 1]);
            }
        }

        int maxSum = 0;
        String[] input = br.readLine().split(" ");
        for (int j = 1; j <= n; j++) {
            maxSum = Math.max(maxSum, Math.max(dp[n - 1][j - 1], dp[n - 1][j]) + Integer.parseInt(input[j - 1]));
        }

        System.out.println(maxSum);
    }
}

마지막층에 있는 숫자들 중에서 나오는 최대 합이 최종적인 최대 합이 되므로 마지막층의 결과 중에서는 최댓값을 찾는 작업이 추가로 필요하다. 그래서 마지막 층은 따로 구현해주었다.