삼각형 위의 최대 경로 - DP

처음엔 무식하게 풀어본다. 이때 해당 문제가 최적 부분 구조를 만족한다는 것을 쉽게 알 수 있다. 예를 들어 임의의 수 A부터 시작한 최대 경로는 A 바로 아래 수부터 시작한 최대 경로(i), A 바로 오른쪽 아래 수부터 시작한 최대 경로(ii) 둘 중 하나다. i나 ii를 구할때 이전에 선택한 값 A는 필요없다. 최적 부분 구조를 만족하므로 DP를 적용해 중복되는 부분 문제를 제거한다.

 

함수 f는 x,y수를 시작으로 한 최대 경로의 숫자 합을 반환한다. 삼각형의 원소 개수만큼 부분 문제가 발생하므로 O(n)의 성능을 보인다.

import java.util.*;
import java.io.*;

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

        for(int t=0; t<testCase; t++) {
             int n = Integer.parseInt(br.readLine());
             int[][] tryangle = new int[n][n];
             int[][] dp = new int[n][n];

             for(int i=0; i<n; i++) {
                 st = new StringTokenizer(br.readLine(), " ");
                 for(int j=0; j<i+1; j++) {
                     tryangle[i][j] = Integer.parseInt(st.nextToken());
                 }
             }
             for(int i=0; i<n; i++)
                 for(int j=0; j<n; j++)
                     dp[i][j] = -1;
             
             int result = f(0,0,tryangle,dp);
             System.out.println(result);
        }
    }

    static int f(int x, int y, int[][] tryangle, int[][] dp) {
        if(x == tryangle.length - 1) return tryangle[x][y];

        if(dp[x][y] != -1) return dp[x][y];

        dp[x][y] = Math.max((f(x+1,y,tryangle,dp) + tryangle[x][y]), (f(x+1,y+1,tryangle,dp) + tryangle[x][y]));
        return dp[x][y];
    }
}