📌 문제

[1932] 정수 삼각형

위 그림은 크기가 5인 정수 삼각형의 한 모습이다.

맨 위층 7부터 시작해서 아래에 있는 수 중 하나를 선택하여 아래층으로 내려올 때, 이제까지 선택된 수의 합이 최대가 되는 경로를 구하는 프로그램을 작성하라. 아래층에 있는 수는 현재 층에서 선택된 수의 대각선 왼쪽 또는 대각선 오른쪽에 있는 것 중에서만 선택할 수 있다.

삼각형의 크기는 1 이상 500 이하이다. 삼각형을 이루고 있는 각 수는 모두 정수이며, 범위는 0 이상 9999 이하이다.

⬇️ 입력

첫째 줄에 삼각형의 크기 n(1 ≤ n ≤ 500)이 주어지고, 둘째 줄부터 n+1번째 줄까지 정수 삼각형이 주어진다.

⬆️ 출력

첫째 줄에 합이 최대가 되는 경로에 있는 수의 합을 출력한다.

💡 코드

합이 최대이기 위해서는 다음 단계에서 그 다음 단계의 두 대각선 수 중 더 큰 합를 선택해야 한다. 말로 설명하니까 좀 이상한데 삼각형을 뒤집어서 생각해보면 좀 쉽다! 이를 점화식으로 표현하면 dp[col][row] = dp[col][row] + Math.max(dp[col+1][row], dp[col+1][row+1])이다. 대각선 요소들에 대한 값은 재귀함수를 통해 호출할 수 있다. 재귀 함수를 통해 첫번째 행부터 마지막 행까지 이동하는데, 결과를 계산하기 위해서는 dp[n-1][]에 triangle[n-1][]의 값과 동일하게 설정해주어야 한다.

또한, 정수의 범위가 0부터 9999이므로 모든 수가 0이면 dp[col][row]의 값이 0일 수 있다. 그래서 dp[][]의 기본값을 int[]의 기본값인 0이 아닌 -1로 정의해줘야 한다.

import java.io.*;
import java.util.*;
public class Main {
	
	static int[][] triangle;
	static int[][] dp;
	static int n;
	
	public static void main(String[] args) throws IOException {
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));

		n = Integer.parseInt(br.readLine());
		triangle = new int[n][n];
		dp = new int[n][n];
		
		for(int i=0;i<n;i++) {
			StringTokenizer st = new StringTokenizer(br.readLine());
		
			for(int j=0;j<=i;j++) {
				triangle[i][j] = Integer.parseInt(st.nextToken());
				dp[i][j] = -1;
			}
		}
		
		for(int i=0;i<n;i++) {
			dp[n-1][i] = triangle[n-1][i];
		}
		
		bw.write(cal(0, 0) + "");
		
		br.close();
		bw.close();
	}
	
	static int cal(int col, int row) {

		if(col == n-1) return dp[col][row];
		
		if(dp[col][row] == -1) {
			dp[col][row] = triangle[col][row] + 
					Math.max(cal(col+1, row), cal(col+1, row+1) );
		}

		return dp[col][row];
	}
}