[BOJ] 백준 1932번 정수 삼각형 (Java)

#1932 정수 삼각형

난이도 : 실버 1

유형 : DP

1932번: 정수 삼각형

▸ 문제

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

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

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

▸ 입력

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

▸ 출력

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

 

문제 풀이  

처음에는 DFS로 그리디하게 현재 최적인 답을 찾아 탐색을 했지만 오답이었다. 반례는 간단했다. 왼쪽과 오른쪽 대각선의 값중 큰 값만 거쳐서 간다고해서 무조건 그 값이 최댓값이 되진 않는다. 

 

왼쪽 그림이 그리디하게 탐색한 경우이고, 오른쪽인 주어진 정수 삼각형의 최댓값이다.

 

반례

오른쪽의 방식으로 답을 구하기 위해서는 모든 경우를 다 조사해줘야 한다. 이렇게하면 O(n^2)이지만 범위도 그리 크지않아서 시간초과가 발생할 우려는 없다.

 

설계

1. 맨 위층부터 시작해 탐색을 시작한다.
2. 층마다 입력값에 주어진 길이만큼 모든 경우의 최댓값을 다 조사한다.dp[i][x] = Math.max(dp[i-1][x-1], dp[i-1][x])+num;
   1. 첫번째와 마지막은 비교할 값이 1개이기 때문에 따로 계산한다. if(x==1) or if(x==i)
3. 마지막 층에서 가장 최댓값을 가지는 수를 출력한다. max = Math.max(max, num);

 

풀이 코드

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.StringTokenizer;

public 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[][] dp = new int[n+1][n+1];
		StringTokenizer st = null;
		for(int i=1; i<n+1; i++) {
			st = new StringTokenizer(br.readLine());
			int x=1;
			while(x<=i && st.hasMoreElements()) {
				int num = Integer.parseInt(st.nextToken());
				
				if(x==1) {
					dp[i][x] = dp[i-1][x] +num;
				}else if(x==i) {
					dp[i][x] = dp[i-1][x-1] +num;
				}else {
					dp[i][x] = Math.max(dp[i-1][x-1], dp[i-1][x])+num;
				}
				x++;
			}
		}
		
		int max =0;
		for(int num : dp[n]) {
			max = Math.max(max, num);
		}
		System.out.println(max);
	}
}