문제

이해

그림과 같은 정수 삼각형이 주어지고 최상단 노드부터 아래로 내려간다. 가능한 경로 중에서 수의 합이 최대가 될 때의 합을 구한다.

예시의 경우, 7 - 3 - 8 - 7 - 5 = 30이 출력된다.

접근

처음에는 단순하게 최대가 되는 경우를 탐색하기로 했다. dfs를 통해 모든 경우를 조사하고 최댓값을 갱신할 수도 있다.

하지만 dfs는 시간복잡도 문제가 발생한다. 가능한 모든 경로를 조사하기 때문에 최악인 경우 n이 500으로 $2^500$ 개가 된다.

따라서, dp와 누적합의 개념을 활용하여 풀이해보았다.

위 그림은 예제의 삼각형을 누적합의 최댓값으로 표현한 것이다. 3층을 예시로 본다면, 3층의 2번은 1을 입력받았다. 3층의 2번으로 도달할 수 있는 경우는 2층의 양쪽의 경우로 2가지가 존재한다.

왼쪽의 경로는 누적합이 10, 오른쪽의 경로는 누적합이 15이기 때문에 3층의 2번은 더 큰쪽이 오른쪽 경로를 선택해 15 + 1 = 16으로 갱신한다.

이런식으로 i층의 수는 i-1층의 누적합 배열에서 가능한 경로 중 더 큰 쪽을 선택해서 갱신하면 된다.

n이 최대 500이기 때문에 입력받는 수는 최대 500 + 499 + ... + 1 = 12750 이 될 수 있다. 따라서, 메모리를 위해 수를 따로 저장하지 않고 입력받는 동시에 처리하도록 설계해보았다.

코드

package java_baekjoon;

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

public class prob1932 {
    static int[] prev_arr;
    static int max = 0;

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

        prev_arr = new int[1];
        prev_arr[0] = Integer.parseInt(br.readLine());

        for (int i = 2; i <= N; i++) {
            int[] arr = new int[i];

            String[] str = br.readLine().split(" ");
            for (int j = 0; j < i; j++) {
                if (j == 0) {
                    arr[j] = prev_arr[0] + Integer.parseInt(str[j]);
                } else if (j == i - 1) {
                    arr[j] = prev_arr[j - 1] + Integer.parseInt(str[j]);
                } else {
                    arr[j] = Math.max(prev_arr[j - 1], prev_arr[j]) + Integer.parseInt(str[j]);
                }
            }

            prev_arr = arr;
        }

        for (int i = 0; i < prev_arr.length; i++) {
            if (max < prev_arr[i]) {
                max = prev_arr[i];
            }
        }

        System.out.println(max);
    }
}

prev_arr[]은 이전 층의 최대 누적합 배열의 정보를 담는다.

1층(편의상 1층부터 시작한다고 가정)은 수가 하나이기 때문에 최초로 초기화해주고 2층부터 반복문을 들어간다.

i층의 가장 자리 노드는 경로가 하나밖에 존재하지 않기 때문에 예외처리를 해주고 그 외의 일반적인 노드는 윗 층의 두 가지 경로가 존재하기 때문에 더 큰쪽을 선택하게 된다.

반복문이 끝나면 prev_arr에는 최하단(n층)의 최대 누적합이 저장된다. 마지막으로 배열을 순회해서 최댓값을 찾으면 된다.

결과

위는 BufferedReader을 이용하고 아래는 Scanner를 이용했다. 메모리, 시간적으로 차이가 있었다.

나는 누적합을 통해 입력받는 동시에 정보를 구하고 이를 다음 반복문에서 사용했다. (관점에 따라선 메모이제이션이라고도 할 수 있겠다.)

https://st-lab.tistory.com/131
하지만 st-lab 님의 풀이는 입력받은 트리의 정보를 2차원 배열을 통해 저장하고 최하단(n층)부터 재귀를 사용한 top-down 방식으로 최대 누적합을 구했다. 이 때는 1층의 노드에 단 한 가지 최대값이 구해진다.

요약하자면 내 풀이는 1층부터 시작해 n개의 최댓값 후보를 구하고 그 중에서 최대값을 뽑았다.
st-lab님의 풀이는 n층부터 시작해 단 한가지로 존재할 수 있는 최대값을 바로 구했다.

비교를 한다면 내 풀이는 전체 트리를 저장하지 않기 때문에 메모리 상으로 장점이 있다. (실제로 메모리 공간을 더 적게 사용했다.)

하지만 끝에서 최댓값을 구하기 위한 반복문을 실행해야 했기 때문에 더 오랜 시간이 걸렸다.

st-lab님의 풀이가 더 깔끔한 것 같다. 나는 풀이할 때 배열의 저장 공간이 최대 12750개가 필요하기 때문에 메모리가 부족할 것이라고 생각했다. 근데 12750개 int형은 51KB밖에 안되니 그냥 저장해도 될 것 같다.