[백준-1932]-[다이나믹프로그래밍] - 정수 삼각형

문제링크 : https://www.acmicpc.net/problem/1932

이문제는 백준-1149번 RGB 구하는 문제와 비슷한 형식을 가진다.

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

한칸 한칸 내려가면서 본인의 최대값을 지니고 있고 

좌우 대각선 위의 값들을 비교해서 그중 큰 값에 자신의 값을 더한게 본인의 최대값이다.

순서대로 가보면 첫번째 값이 7 이 들어오고 7의 최대값은 7이다.

두번째 줄에 3 8 이 들어오고 각각의 최대 값을 구하면

3 의 왼쪽 위     0

3 의 오른쪽 위  7

8 의 왼쪽 위     7

8 의 오른쪽 위  0

3의 최대값은 10

8의 최대값은 15

로 아래와 같은 삼각형이 나온다.

    7

10  15

세번째 줄은 8, 1, 0 이 입력 됐고

같은 방법으로 계산하면 정수 피라미드는 아래처럼 나온다.

    7

10  15

     18  16  15 

네번째 줄은 2, 7, 4, 4  가 입력 됐고

    7

10  15

     18  16  15 

  20 25  20 20

다섯번째 줄은 4, 5, 2, 6, 5 가 입력 됐고

     7

 10  15

      18  16  15 

   20 25  20 20

24 30  27  26  25

그래서 최대 값은 30 이 나오게 된다.

계산 되는 점화식은 아래와 같이 구해진다. 

LEFT  = sum[i-1][j-1] + arr[i][j]

RIGHT = sum[i-1][j] + arr[i][j]

sum[i][j] = max(left, right) + arr[i][j]

점화식도 구했으니 이제 코딩을  해보자

소스

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.StringTokenizer;
 
public class E_1932 {
 
    public static void main(String[] args) throws NumberFormatException, IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        StringTokenizer st = null; 
        
        int num = Integer.parseInt(br.readLine());
        
        int arr[][] = new int[num+1][num+1];
        long sum[][] = new long[num+1][num+1];
        long max = Long.MIN_VALUE;
        for(int i=1; i <= num; i++) {
            st = new StringTokenizer(br.readLine());
            for(int j=1; j <= i; j++) {
                arr[i][j] = Integer.parseInt(st.nextToken());
                // 왼쪽 위가 있을경우
                long left = sum[i-1][j-1] + arr[i][j];
                // 오른쪽 위가 있을경우
                long right = sum[i-1][j] + arr[i][j];
                
                sum[i][j] = Math.max(left, right);
                
                max = Math.max(sum[i][j], max);
            }
        }
        
        System.out.println(max);
    }
 
}