[BaekJoon] 1932 정수 삼각형

1.  문제 링크

https://www.acmicpc.net/problem/1932

2.  문제

요약

• 크기가 n인 정수 삼각형에서 맨 위층부터 시작하여 아래에 있는 수 중 대각선 왼쪽 또는 대각선 오른쪽에 있는 수 중 하나를 선택하여 내려오는데, 이 때 선택된 수의 합이 최대가 되는 경로를 구하는 문제입니다.
• 입력: 첫 번째 줄에 1보다 크거나 같고 500보다 작거나 같은 정수 삼각형의 크기 n이 주어지고 두 번째 줄부터 n개의 줄에는 0보다 크거나 같고 9999보다 작거나 같은 정수인 정수 삼각형의 수들이 주어집니다.
• 출력: 첫 번째 줄에 최대가 되는 경로에 있는 수의 합을 출력합니다.

3.  소스코드

import java.io.BufferedReader;
import java.io.BufferedWriter;
import java.io.IOException;
import java.io.InputStreamReader;
import java.io.OutputStreamWriter;
import java.util.Arrays;

public class Main {
    static int num;
	static int[][] triangle;
	static Integer[][] dp;
	public int findMaxNum(int depth, int index) {
		if(depth == num - 1) {
			return dp[depth][index];
		}
		if(dp[depth][index] == null) {
			dp[depth][index] = Math.max(findMaxNum(depth + 1, index), findMaxNum(depth + 1, index + 1)) + triangle[depth][index];
		}
		return dp[depth][index];
	}
	
	public int getMaxNum() {
		for(int i = 0; i < triangle.length; i++) {
			dp[dp.length - 1][i] = triangle[dp.length - 1][i];
		}
		return findMaxNum(0, 0);
	}
	
	public static void main(String[] args) throws IOException {
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));
		num = Integer.parseInt(br.readLine());
		triangle = new int[num][num];
		dp = new Integer[num][num];
		for(int i = 0; i < num; i++) {
			String[] input = br.readLine().split(" ");
			for(int j = 0; j < input.length; j++) {
				triangle[i][j] = Integer.parseInt(input[j]);
			}
		}
		br.close();
		Main m = new Main();
		bw.write(m.getMaxNum() + "\n");
		bw.flush();
		bw.close();
	}
}

4.  접근

• 해당 문제는 DP를 이용하여 해결할 수 있습니다.
• 주어진 정수 삼각형의 값을 저장하기 위한 2차원 배열 triangle과 경로의 합을 저장하는 2차원 배열 dp를 생성합니다.
• dp 배열의 마지막 행에는 triangle의 마지막 행의 값들, 즉 삼각형에서 가장 아래 줄의 값들을 넣어 초기화시켜줍니다.
• 위에서부터 탐색해가면서 정수 삼각형에서 최대가 되는 경로에 있는 수의 합을 구합니다.
• dp 배열을 위에서부터 탐색하였을 때, 가장 마지막 줄을 제외하고는 모두 비어있기 때문에 재귀호출로 인해 계속해서 아래 행으로 내려가 탐색하게 되고 뒤에서 두 번째 행의 각 값에서 그 아래의 양쪽 값 중 최댓값을 선택합니다.
• 선택한 최댓값과 현재 값을 더한 값이 해당 위치에서의 최대가 되는 경로에 있는 수의 합이 됩니다.
• 위 방식을 바탕으로 아래에서부터 위로 값이 채워지면서 배열 dp의 가장 위 행의 값이 정수 삼각형에서 최대가 되는 경로에 있는 수의 합이 됩니다.
• 위 방법을 점화식으로 나타내어 코드로 변환하면 아래와 같은 재귀함수가 생성됩니다.

public int findMaxNum(int depth, int index) {
	if(depth == num - 1) {
		return dp[depth][index];
	}
	if(dp[depth][index] == null) {
		dp[depth][index] = Math.max(findMaxNum(depth + 1, index), findMaxNum(depth + 1, index + 1)) + triangle[depth][index];
	}
	return dp[depth][index];
}

• 위 점화식을 바탕으로 최대가 되는 경로에 있는 수의 합을 구합니다.

1. 정수 삼각형의 값들을 담을 triangle 배열을 생성하고 값들을 담으며 경로의 합을 담는 dp 배열을 생성한 후, dp의 가장 아래의 행을 triagle 배열의 가장 아래 행의 값들로 초기화시킵니다.
2. 위에서 구한 점화식을 바탕으로 정수 삼각형에서 최대가 되는 경로에 있는 수의 합을 구합니다.
   1. 만약 행이 가장 마지막 행까지 도달했다면 해당 행에서 해당 열의 값을 반환합니다.
   2. 만약 현재 행과 열의 값이 null이라면 재귀함수를 통해 해당 위치 아래 양쪽 두 값 중 큰 값을 구하고 해당 값에 현재 위치의 수를 더하여 현재 위치에서의 값을 설정합니다.
   3. 재귀함수를 통해 탐색을 완료한 후, dp 배열에서 가장 위 행의 첫 번째 값을 반환합니다.
3. 2번의 점화식을 통해 반환된 값이 정수 삼각형에서 최대가 되는 경로에 있는 수의 합이 되어 해당 값을 출력합니다.