삼각형 위의 최대 경로

풀이

무식하게 풀기

우선 무식하게 푸는 방법을 생각해보겠습니다. 모든 경로를 다 확인하는 것이므로 한번 내려갈 때 2가지 경우의 수가 있으므로 $n$개의 가로줄이 있을 때 가능한 경로의 수는 $2^{n - 1}$입니다. $n$이 100이라면 절대 해결할 수 없는 수치입니다.

메모이제이션 적용하기

우리는 $(0, 0)$의 위치에서 맨 밑으로 내려갔을 때 얻을 수 있는 최댓값을 구하려고 합니다. 따라서 현재 위치와 지금까지 만난 숫자들의 합을 인자로 넣어 호출하는 함수를 만들면 현재 위치의 숫자와 지금까지 만난 숫자들의 합을 더해서 반환하는 함수를 만들어봅시다.
$pathSum(row, column, sum) =$ 현재 위치가 $(row, column)$이고, 지금까지 만난 수의 합이 $sum$일 때, 이 경로를 맨 아래줄까지 연장해서 얻을 수 있는 최대 합을 반환한다.
이때 아래쪽으로 내려갔을 때와 오른쪽으로 내려갔을 때의 최대 합을 각각 $path()$를 이용해 표현하면 다음과 같은 점화식을 얻을 수 있습니다.
$path(row, column, sum) = \max\begin{cases}path(row + 1, column, sum+triangle[row][column])\\path(row + 1, column + 1, sum + triangle[row][column])\end{cases}$
아래는 이 함수를 구현한 코드입니다.

// MAX_NUMBER: 한 칸에 들어갈 숫자의 최대치
public int n, triangle[100][100];
public int cache[100][100][MAX_NUMBER*100+1];
// (row, column) 위치까지 내려오기 전에 만난 숫자들의 합이 sum 일 때
// 맨 아래줄까지 내려가면서 얻을 수 있는 최대 경로를 반환한다.
public int pathSum(int row, int column, int sum) {
    // 기저 사례: 맨 아래 줄까지 도달했을 경우
    if (y == n - 1) return  sum + triangle[row][column];
    // 메모이제이션
    if (cache[row][column][sum] != -1) return cache[row][column][sum];
    sum += triangle[row][column];
    return cache[row][column][sum] = Math.max(pathSum(row + 1, column + 1, sum), pathSum(row + 1, column, sum));
}

이렇게 구현할 경우 MAX_NUMBER의 값은 마지막 행을 제외한 각 행에서 최댓값의 합이 됩니다. 만약 각 행의 최댓값이 100,000이고 $n$이 100일 경우 int cache[100][100][100000*100+1]배열을 할당해야 합니다. int형 데이터를 저장하려면 4바이트가 필요하므로 $4\times100\times100\times100,000 + 4 = 40,000,000,004$바이트가 필요합니다. 메모리 제한이 $65,536,000$바이트이므로 택도 없이 부족합니다.

최적 부분 구조

여기서 좋은 최적 부분 구조를 찾는다면 효율적인 알고리즘을 구현할 수 있습니다. 우리는 특정 위치에서 시작했을 때 가장 아래 행에 도달했을 때 얻을 수 있는 최댓값은 특정 위치까지 도달하면서 만나는 숫자들의 합과는 상관이 없습니다. 즉, 지금까지 어떤 경로로 도달했건 남은 부분 문제는 항상 최적으로 풀어도 상관 없다는 뜻입니다. 이런 문제는 최적 부분 구조가 성립합니다. 최적 부분 구조란 각 부분 문제의 최적해만 있으면 전체 문제의 최적해를 쉽게 얻어낼 수 있는 구조입니다. 따라서 위에서 구현한 int pathSum(int row, int column, int sum) 함수를 int pathSum(int row, int column)으로 바꾸고 현재 위치에서 맨 아래 행까지 내려갔을 때 얻을 수 있는 최댓값을 반환하도록 바꿉니다. 전체 경로의 최대 합을 반환하는 것이 아니라 부분 경로의 최대합을 반환하는 것입니다. 이 동작은 다음과 같은 점화식으로 정의할 수 있습니다.
$path(row, column)=triangle[row][column]+\max\begin{cases}path(row + 1, column)\\path(row + 1, column + 1)\end{cases}$

시간 복잡도 분석

위의 알고리즘에서 부분 문제의 수는 $O(n^2)$이고 각 부분 문제를 계산하는 데는 상수 시간밖에 안 걸리기 때문에 전체 시간 복잡도는 $O(n^2)$이 됩니다.

구현

import java.util.*;

public class Main {

    // 삼각형의 크기와 배열
    public static int n, triangle[][];
    // 캐시
    public static int cache[][];
    // 답
    public static int result;

    // 입력 데이터를 처리하는 메소드
    public static void input(Scanner scanner) {
        n = scanner.nextInt();
        triangle = new int[n][n];
        int maxNum = 0;
        for (int i = 0; i < n; i++) {
            for (int j = 0; j <= i; j++) {
                triangle[i][j] = scanner.nextInt();
                maxNum = Math.max(maxNum, triangle[i][j]);
            }
        }
        cache = new int[n][n];
    }

    // 문제를 해결하는 메소드
    public static void solve() {
        result = pathSum(0, 0);
    }

    // (row, column) 위치부터 맨 아래줄까지 내려가면서 얻을 수 있는 최대 경로의 합을 반환하는 메소드
    public static int pathSum(int row, int column) {
        // 기저 사례
        if (row == n - 1) return triangle[row][column];
        // 메모이제이션
        if (cache[row][column] != 0) return cache[row][column];

        return cache[row][column] = Math.max(pathSum(row + 1, column), pathSum(row + 1, column + 1)) + triangle[row][column];
    }

    // 답을 출력하는 메소드
    public static void output() {
        System.out.println(result);
    }

    public static void main(String[] args) {
        Scanner scanner = new Scanner(System.in);
        int testCase = scanner.nextInt();
        for (int i = 0; i < testCase; i++) {
            input(scanner);
            solve();
            output();
        }
    }
}

회고

최적 부분 구조를 잘 이해해야 한다는 것을 알았습니다.

참고문헌: 구종만, 프로그래밍 대회에서 배우는 알고리즘 문제해결전략, 인사이트, (2012)