[동적 계획법] 백준 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번째 줄까지 정수 삼각형이 주어진다.

 

입력 예시	출력 예시
5 7 3 8 8 1 0 2 7 4 4 4 5 2 6 5	30

 

📝 문제 해결

테이블 정의

arr[][]: 초기 정수 삼각형 정보를 담는 테이블

dp[][] : 최대 합을 저장하는 테이블

 

점화식 찾기

• 왼쪽 위
• 바로 위

이 문제에서 특정한 위치로 도달하기 위해서는 이 두가지 경우만 가능하다. 따라서 모든 위치를 기준으로 이전 위치로 가능한 두가지 위치까지의 최적의 합 중에서 더 큰 합을 가지는 경우를 선택하면 된다.

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

 

💻 코드

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

public class BOJ1932 {
	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+1][n+1];
		int dp[][] = new int[n+1][n+1];
		
		for(int i=1; i<=n; i++) {
			StringTokenizer st = new StringTokenizer(br.readLine());
			for(int j=1; j<=i; j++) {
				arr[i][j] = Integer.parseInt(st.nextToken());
			}
		}
		
		for(int i=1; i<=n; i++) {
			for(int j=1; j<=n; j++) {
				dp[i][j] = arr[i][j] + Math.max(dp[i-1][j-1], dp[i-1][j]);
			}
		}
        
		int max=0;
		for(int i=1; i<=n; i++) {
			if(max < dp[n][i]) max = dp[n][i]; 
		}
		
		System.out.println(max);
	}
}