TRIANGLEPATH 삼각형 위의 최대 경로 / ALGOSPOT

문제링크 : https://algospot.com/judge/problem/read/TRIANGLEPATH
제출링크 : https://algospot.com/judge/submission/detail/655087
자바소스 : https://github.com/skysign/WSAPT/blob/master/ALGOSPOT/TRIANGLEPATH/src/Main.java

아래로 내려가거나, 오른쪽 아래 2가지 방향으로 내려간다는 점에서, recurrence relation을 아래와 같이 정의 할 수 있습니다.

• 트라이앵글의 높이가 N
• 트라이앵글로 입력된 데이터를 map[][] 행렬이라고 가정

\begin{aligned}
dp_{i,j} = max(dp_{i-1,j} + map_{i,j}, dp_{i-1,j-1} + map_{i,j}) \\
\end{aligned}

위의 점화식에서 알 수 있듯이, 현재 dp_{i,j} 계산하기 위해서는, dp_{i,j}에 바로 앞에 있는 값이 필요합니다.
이럴 때에는, 코드를 좀더 간단하게 하기 위해서, 트라이앵글의 높이 N 보다 1 큰 상태로, 배열을 만들어주세요.
트라이앵글의 데이터는 map[1][1] 부터 채워 넣고, dp[?][0] 는 모두 0으로 초기화 합니다.

가장 첫번째로 계산하는 i,j 1,1 의 경우에, 아래와 같이 계산하게 됩니다. N+1 크기로 배열을 잡았기 때문에,
dp[0,0], dp[0,1] 가 존재하고, 0으로 초기화 되어 있으므로, 계산 결과에 영향을 주지 않습니다.
\begin{aligned}
dp_{1,1} = max(dp_{0,1} + map_{1,1}, dp_{0,0} + map_{1,1}) \\
\end{aligned}

이렇게 하면, 루프의 시작을 i=1 j=1 부터 하게 되면, 루프안에 if 문을 줄일 수 있습니다.

for(i=1, i<=N; ++i) {
    for(int j=1; J<=N; ++j) {

위의 이중루프가 끝나게되면, dp[N][?] 열에 있는 값중 가장 큰 값이 정답이 됩니다.

import java.util.Scanner;

/**
 * TRIANGLEPATH 삼각형 위의 최대 경로 / ALGOSPOT
 * 문제링크 : https://algospot.com/judge/problem/read/TRIANGLEPATH
 * 제출링크 : https://algospot.com/judge/submission/detail/655087
 */
public class Main {
    Scanner sc = new Scanner(System.in);

    public void solve() {
        int T = sc.nextInt();
        int r = 0;

        for(int t=0; t<T; ++t) {
            int N = sc.nextInt();
            int[][] map = new int[N+1][N+1];
            for(int i=1; i<=N; ++i) {
                for(int j=1; j<=i; ++j) {
                    map[i][j] = sc.nextInt();
                }
            }

            r = maxSum(map, N);
            System.out.println(r);
        }
    }

    public int maxSum(int[][] map, int N) {
        int[][] dp = new int[N+1][N+1];

        for(int i=1; i<=N; ++i) {
            for(int j=1; j<=i; ++j) {
                dp[i][j] = Math.max(dp[i-1][j] + map[i][j], dp[i-1][j-1] + map[i][j]);
            }
        }

        int max = 0;
        for(int j=1; j<=N; ++j)
            max = Math.max(max, dp[N][j]);

        return max;
    }

    public static void main(String[] args) {
        Main main = new Main();
        main.solve();
    }
}