삼각형 위의 최대 경로 개수 세기 (난이도: 중)

( 여기서 먼저 이 알고리즘을 보기전에 아래의 사이트를 먼저 학습하고 보는 것을 추천합니다. )

삼각형 위의 최대 경로 (난이도: 하) (tistory.com)

삼각형 위의 최대 경로 (난이도: 하)

 

 

 

 

1. 문제 설명

(1) "삼각형 위의 최대 경로"에서는 최대 경로의 합을 구했지 경로 자체는 구하지 않았다.

 

(2) 예를 들어, 아래의 그림 삼각형에는 세 개의 최대 경로 {9, 7, 2, 6}, {9, 7, 3, 5}, {9, 7, 3, 5}가 존재하며

합은 모두 24가 됩니다.

 

(3) 만약 N이 커질 경우에 최대 경로의 수를 찾는 프로그램을 작성하시오.

 

 

 

 

2. 입출력 조건 및 예제

입력 조건

X

 

출력 조건

X

 

 

입력 예제

2

4

9 0 0 0
5 7 0 0
1 3 2 0
3 5 5 6

5

6 0 0 0 0
1 2 0 0 0
3 7 4 0 0
9 4 1 7 0
2 7 5 9 4

 

출력 예제

3

1

 

 

 

 

3. 제약 조건

X

 

 

 

 

4. 가정법

X

 

 

 

 

5. 기저 사례

(1) y가 N-1의 위치가 도달했을 경우

 

 

 

 

6. 코드

public class TRIPATHCNT {
    private static BufferedReader sc = new BufferedReader(new InputStreamReader(System.in));
    private static StringBuilder sb = new StringBuilder();

    private static int[][] A;
    private static int N;

    private static int[][] countCache;
    private static int[][] pathCache;

    public static void main(String[] args) throws IOException {
        StringTokenizer st;
        int C = Integer.parseInt(sc.readLine());

        for(int i=0; i<C; i++) {
            countCache = new int[101][101];
            pathCache = new int[101][101];

            N = Integer.parseInt(sc.readLine());
            A = new int[N][N];

            for(int y=0; y<N; y++) {
                st = new StringTokenizer(sc.readLine());
                for(int x=0; x<N; x++) {
                    A[y][x] = Integer.parseInt(st.nextToken());
                }
            }

            sb.append(solve(0, 0)+"\n");
        }
        System.out.println(sb);
    }

    private static int solve(int y, int x) {
        if(y==N-1) return 1;

        if(countCache[y][x] != 0) return countCache[y][x];

        // 만약 (y+1, x+1)이 더 크다면 아래 오른쪽에서 시작
        // 만약 (y+1, x)이 더 크다면 아래에서 시작
        // 단, 둘 다 최대 경로가 같다면 둘다 카운트 ++
        if(path(y+1, x+1) >= path(y+1,x)) countCache[y][x] += solve(y+1, x+1);
        if(path(y+1, x+1) <= path(y+1,x)) countCache[y][x] += solve(y+1, x);

        return countCache[y][x];
    }

    // 삼각형 위의 최대 경로 합 구하는 메서드
    private static int path(int y, int x) {
        if(y==N-1) return A[y][x];

        if(pathCache[y][x] != 0) return pathCache[y][x];

        return pathCache[y][x] = Math.max(path(y+1, x)+A[y][x], path(y+1, x+1)+A[y][x]);
    }
}

 

 

 

 

7. 점화식