백준 1932번 정수 삼각형(JAVA)

1932번: 정수 삼각형

문제

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

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

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

 

입력

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

 

출력

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

 

풀이

arr 배열

7
3	8
8	1	0
2	7	4	4
4	5	2	6	5

 

dp 배열

-1	-1	-1	-1	-1
-1	-1	-1	-1	-1
-1	-1	-1	-1	-1
-1	-1	-1	-1	-1
4	5	2	6	5

arr 배열과 dp 배열의 초기 상태는 위와 같다.

 

-1	-1	-1	-1	-1
-1	-1	-1	-1	-1
-1	-1	-1	-1	-1
-1	-1	-1	-1	-1
4	5	2	6	5

(0, 0)을 시작으로 탐색을 시작하면 (1, 0)과 (1, 1) 중 최대값을 찾으려 할 것이다. 하지만 이들도 아직 탐색을 하지 않아 다음 행으로 내려간다.

-1	-1	-1	-1	-1
-1	-1	-1	-1	-1
-1	-1	-1	-1	-1
-1	-1	-1	-1	-1
4	5	2	6	5

(1, 0)은 (2, 0)과 (2, 1) 중 최대값을 찾으려 할 것이고, (1, 1)은 (2, 1)과 (2, 2) 중 최대값을 찾으려 할 것이다. 마찬가지로 탐색을 하지 않아 다음 행으로 내려간다.

...

-1	-1	-1	-1	-1
-1	-1	-1	-1	-1
-1	-1	-1	-1	-1
-1	-1	-1	-1	-1
4	5	2	6	5

마지막 행에 도달하면 유효한 값을 찾을 수 있다.

 

-1	-1	-1	-1	-1
-1	-1	-1	-1	-1
-1	-1	-1	-1	-1
5 + 2	-1	-1	-1	-1
4	5	2	6	5

dp[3][0]은 dp[4][0]과 dp[4][1] 중 더 큰 값인 5와 arr[3][0]를 더한 7이 된다.

 

-1	-1	-1	-1	-1
-1	-1	-1	-1	-1
-1	-1	-1	-1	-1
5 + 2	5 + 7	6 + 4	6 + 4	-1
4	5	2	6	5

 

-1	-1	-1	-1	-1
-1	-1	-1	-1	-1
12 + 8	12 + 1	10 + 0	-1	-1
7	12	10	10	-1
4	5	2	6	5

 

-1	-1	-1	-1	-1
20 + 3	13 + 8	-1	-1	-1
20	13	10	-1	-1
7	12	10	10	-1
4	5	2	6	5

 

23 + 7 = 30	-1	-1	-1	-1
23	21	-1	-1	-1
20	13	10	-1	-1
7	12	10	10	-1
4	5	2	6	5

 

동일한 과정으로 최종 값을 구하는 과정이다. 결국 dp[r][c]의 최대값은 Math.max(dp[r+1][c], dp[r+1][c+1]) + arr[r][c]이다. 이때 dp[r+1][c]나 dp[r+1][c+1]를 재귀탐색하기 위해 dp[r+1][c] 대신 func(r+1, c)를 사용한 것이다.

따라서 dp[r][c] = Math.max(func(r+1, c), func(r+1, c+1)) + arr[r][c]가 된다.

 

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

public class Main {
	static int[][] arr;
	static int[][] dp;
	static int N;
	
	public static void main(String[] args) throws NumberFormatException, IOException {
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		N = Integer.parseInt(br.readLine());
		arr = new int[N][N]; //정수 삼각형 수들을 저장할 배열을 초기화한다
		dp = new int[N][N]; //누적합을 저장할 배열을 초기화한다
		
		for(int i=0; i<N; i++) {
			String[] line = br.readLine().split(" ");
			for(int j=0; j<i+1; j++) 
				arr[i][j] = Integer.parseInt(line[j]);
		}
		
		// 값의 범위에 0이 포함된다. 탐색한 위치인지 구별하기 위해 -1로 채워준다
		for(int[] temp : dp) 
			Arrays.fill(temp, -1);
		
		for(int i=0; i<N; i++) 
			dp[N-1][i] = arr[N-1][i];
		
		System.out.println(func(0, 0)); 
	}
	
	static int func(int r, int c) { //행(뎁스), 열  
		if(r == N - 1) return dp[r][c]; //마지막 행일 경우 현재 값을 반환한다
		
		if(dp[r][c] == -1) //아직 탐색하지 않은 위치일 때
			dp[r][c] = Math.max(func(r+1, c), func(r+1, c+1)) + arr[r][c];
		
		return dp[r][c]; //현재 위치에서의 max 값을 반환한다
	}

}