[백준] 1932번: 정수 삼각형 (Java/자바)

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

1932번: 정수 삼각형

 

문제

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

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

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

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

 

입력

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

 

출력

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

 

예제 입력 1

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

 

예제 출력 1

30

 

알고리즘 분류

• 다이나믹 프로그래밍

 

풀이

다이나믹 프로그래밍 문제 중 정답률이 높은 문제를 선택하여 알고리즘에 대한 두려움을 극복하고자 했으나... 로직을 어떻게 구현해야 경로에 있는 수의 합을 최대로 출력 할 수 있는지 아이디어가 떠오르지 않아 많은 고민을 했다. 이번 다이나믹 프로그래밍 문제도 점화식을 세울 수 있는 알고리즘이었고, 위에서 아래로 내려가면서 경로를 찾는게 아닌, 가장 아래부터 최대 합을 찾아 위로 올라가는 경로를 찾아가면 되는 것이었다.

우선 이차원 배열을 선언하여 정수 삼각형의 값들을 입력한다. 입력된 값들을 한 줄로 받아 띄어쓰기를 기준으로 배열 원소마다 정수를 할당하기 위해 StringTokenizer 클래스를 선언한다. 그리고 현재값( arr[i-1][j] )을 기준으로 대각선 왼쪽 아래와 대각선 오른쪽 아래 중 최대값이 되도록 선택하기 위해서 아래와 같은 점화식을 세웠다.

arr[i-1][j] += Math.max(arr[i][j], arr[i][j+1])

점화식을 세울 때, 배열의 범위를 벗어나거나 음수가 발생할 수 있기 때문에  for문과 Math.max( ) 로 최대값을 설정하는 곳에서 에러가 나지 않도록 주의가 필요하다.

 

소스

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

class Main
{
	public static void main (String[] args) throws IOException
	{
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		
		int n = Integer.parseInt(br.readLine());
		int[][] arr = new int[n][];
		
		for (int i=0; i<n; i++) {
			StringTokenizer st = new StringTokenizer(br.readLine());
			arr[i] = new int[i + 1];
			for (int j=0; j<=i; j++) {
				arr[i][j] = Integer.parseInt(st.nextToken());
			}
		}
		
		for (int i=n-1; i>0; i--) {
		    for (int j=0; j<i; j++) {
		        arr[i-1][j] += Math.max(arr[i][j], arr[i][j+1]);
		    }
		}
		
		System.out.println(arr[0][0]);
	}
}