동적 계획법 예제(6). 백준 [1932] 정수 삼각형

백준[1932] - 정수 삼각형

오랜만에 DP 문제를 풀어보았다.

정수 삼각형을 입력받아 저장한 뒤, 최종적으로 가장 큰 수를 만들어 가는 문제이다.
단, 선택할 수는 다음행의 수 중, 왼쪽, 오른쪽 둘 중 하나만 선택 가능하다.

즉, 7에서 선택할 수 있는 수는 3, 8 둘 중 하나이다.
이런 방식으로 하나씩 더해 나가 가장 큰 수를 만들면 된다. 

얼핏 보면, 선택할 수 있는 수 중에 큰 수를 선택해서 진행하면 되는 탐욕 법 문제로 볼 수 있다. 
하지만, 그 다음 상황은 모르기 때문에 탐욕 법은 항상 올바른 답을 주지 않는다.

따라서, 동적 계획법을 이용하여 답을 구해내면 된다.

다음은 Java로 작성한 코드이다.

import java.util.Scanner;

public class Triangle {

	public static void main(String[] args) {
		//입력
		Scanner scan = new Scanner(System.in);
		int n = scan.nextInt();

		//정수 삼각형 2차원 배열
		int[][] triangle =  new int[n][n];
		
		//정답 2차원 배열 - 메모제이션 활용
		int[][] solution =  new int[n][n];

		//입력 받기 
		for (int i = 0; i < n; i++) {
			for (int j = 0; j <= i; j++) {
				triangle[i][j] = scan.nextInt();
			}
		}

		//기저 조선 
		solution[0][0] = triangle[0][0];

		
		//문제 풀이
		for (int i = 1; i < n; i++) {
			for (int j = 0; j <= i; j++) {
				if(j>0) {
					solution[i][j] = triangle[i][j] + Math.max(solution[i-1][j],solution[i-1][j-1]);
				}else {
					solution[i][j] = solution[i-1][j] + triangle[i][j];
				}
			}
		}

		//최대값 찾기 
		int max=0;
		for (int i = 0; i < n; i++) {
			for (int j = 0; j <= i; j++) {
				max = Math.max(max, solution[i][j]);
			}
		}
		
		System.out.println(max);
	}

}

메모제이션을 이용하여 문제를 간단하게 풀 수 있다.
ArrayList를 이용할지 다른 자료구조를 이용할지 고민하다 배열에 저장하면 규칙을 쉽게 찾을 수 있다는 것을 발견했다.
배열에 왼쪽부터 차례대로 저장한다고 하면, 자신이 선택될 수 있는 요소는 j가 같거나, j가 자기보다 1 작은 경우(j-1)이다. 

따라서 solution을 정하는 코드는 다음과 같다.

solution[i][j] = triangle[i][j] + Math.max(solution[i-1][j],solution[i-1][j-1]);

하지만, 배열의 특성상 index에 대한 예외를 처리해 주어야 한다.
inedex 오류가 발생하는 상황은 j가 0인 경우이다. 따라서 이러한 경우에는 자신이 선택될 수 있는 경우는 단 한 가지이기 때문에, 다음과 같이 구할 수 있다.

solution[i][j] = solution[i-1][j] + triangle[i][j];