[백준 | Java] 1932 정수 삼각형

내 풀이

우선 삼각형의 꼭대기부터 시작해 갈 수 있는 아래 두 수 중, 더 큰 수로 계속 가다보면 끝까지 도착했을 때 합이 최대가 되는 수가 될 것이라 예상했다. 이 방법으로 예제를 풀어보니 오답이었다.
위 쪽에선 가장 큰 수만을 따라갔어도, 다른 경로에서 같은 레벨의 수 중 크기 차이가 많이 나는 수가 있다면 답이 틀린다.

이후, 여러개의 작은 문제로 큰 하나의 문제를 해결하는 다이나믹 프로그래밍 알고리즘을 떠올렸다.

방법1

삼각형 가장 아래의 각 요소마다 더한 값 중, 가장 큰 값을 따라가다가 꼭대가기 나오면, 해당 경로를 모두 더한 값이 합이 최대가 되는 값이 된다.

1. 4~5번째 줄 사이 더한 값 중, 12가 가장 큼
2. 3~4번째 줄 사이 더한 값 중, 15가 가장 큼
3. 2~3번째 줄 사이 더한 값 중, 11이 가장 큼
4. 꼭대기 도착
5. 12 + 15 + 11 + 10 - 7 - 8 - 3 = 30
   => 더한 값을 모두 더하고, 겹치는 값인 7, 8, 3을 빼줌

방법2

삼각형의 n-2번쨰 줄부터 각 요소에서 갈 수 있는 두 개의 수 중, 더 큰 숫자를 해당 요소에 더한 후 계속 위로 올라가다가 꼭대기를 만나면 합이 최대가 되는 값이 반환된다.

코드

방법2

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));
        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());
            }
        }
        for (int i = n - 2; i >= 0; i--) {
            for (int j = 0; j <= i; j++) {
                triangle[i][j] += Math.max(triangle[i + 1][j], triangle[i + 1][j + 1]);
            }
        }
        System.out.println(triangle[0][0]);
    }
}