[AlgoSpot] 삼각형 위의 최대 경로

문제 설명

알고리즘 문제 해결 전략 - 동적 계획법
문제 링크

문제 풀이

• 동적 계획법을 이용하여 풀이하였다.
• dp(x, y) : (x, y)에서 시작해서 맨 아래줄까지 내려가는 모든 경로 중 최대합.

소스 코드 (JAVA)

import java.util.Scanner;

public class Main {
    public static int C, N;
    public static int[][] map;
    public static int[][] max;

    public static int dp(int x, int y) {
        if (x == N - 1) return map[x][y];
        if (max[x][y] != 0) return max[x][y];
        return max[x][y] = Math.max(dp(x+1, y), dp(x+1, y+1)) + map[x][y];
    }

    public static void main(String[] args) {
        map = new int[101][101];
        max = new int[101][101];
        Scanner scanner = new Scanner(System.in);
        C = scanner.nextInt();
        for (int c = 0; c < C; c++) {
            N = scanner.nextInt();
            for (int i = 0; i < N; i++) {
                for (int j = 0; j <= i; j++) {
                    map[i][j] = scanner.nextInt();
                    max[i][j] = 0;
                }
            }
            System.out.println(dp(0,0));
        }
    }
}