삼각형 위의 최대 경로 개수 세기

풀이

이전에 풀었던 삼각형 위의 최대 경로 찾기 문제를 돌이켜 봅시다. 삼각형 위의 최대 경로 찾기 문제에서는 각 위치에서 맨 밑으로 내려갔을 때 최대한 얻을 수 있는 값을 구했습니다. 우리가 지금 구하고 싶은 것은 최대한 얻을 수 있도록 하는 경로의 개수를 구하는 것입니다. 이전에 풀었던 코드의 캐시를 이용한다면 쉽게 해결할 수 있습니다. 내려갈 때 어디로 내려가야 할지 쉽게 알 수 있기 때문입니다. $(0,0)$에서 시작하는 최대 경로는 $(1,0)$과 $(1,1)$ 중 더 큰 값을 가진 곳으로 내려가면 됩니다. 만약 같다면 둘 다 내려갈 수 있습니다. 함수 $count(row, column)$을 정의합시다.
$count(row,column)=(row,column)$에서 시작해 맨 아래줄까지 내려가는 최대 경로의 수
이 경로에서 $(row, column)$의 다음 칸은 이전 문제의 코드에서 정의했던 $path(row + 1, column)$과 $path(row + 1, column + 1)$ 중 어느 쪽이 더 큰지에 따라 결정됩니다. 이 로직을 점화식으로 옮기면 다음과 같습니다.
$count(row,column)=max\begin{cases}count(row+1,column) (path(row+1,column)>path(row+1,column+1))\\count(row+1,column+1)(path(row+1,column)<path(row+1,column+1))\\count(row+1,column)+count(row+1,column+1)(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;
    public static int[][] triangle, cache, countCache;
    public static int result;

    public static void input(Scanner scanner) {
        n = scanner.nextInt();
        triangle = new int[n][n];
        cache = new int[n][n];
        countCache = new int[n][n];

        for (int i = 0; i < n; i++) {
            for (int j = 0; j < i + 1; j++) {
                triangle[i][j] = scanner.nextInt();
            }
        }
    }

    public static void solve() {
        result = count(0, 0);
    }

    // (row, column)에서 시작해서 맨 아래줄까지 내려가는 경로 중 최대 경로를 반환하는 메소드
    public static int path(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] = triangle[row][column] + Math.max(path(row + 1, column), path(row + 1, column + 1));
    }

    // (row, column)에서 시작해서 맨 아래줄까지 내려가는 경로 중 최대 경로의 개수를 반환하는 메소드
    public static int count(int row, int column) {
        // 맨 아래줄에 도달한 경우
        if (row >= n - 1) return 1;
        // 메모이제이션
        if (countCache[row][column] != 0) return countCache[row][column];

        if (path(row + 1, column) >= path(row + 1, column + 1)) countCache[row][column] += count(row + 1, column);
        if (path(row + 1, column) <= path(row + 1, column + 1)) countCache[row][column] += count(row + 1, column + 1);
        return countCache[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();
        }
    }
}

회고