[BOJ] 백준 1932 정수 삼각형

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

 Input 

5

7

3 8

8 1 0

2 7 4 4

4 5 2 6 5

 

 Output 

30

▶ 동적계획법(Dynamic Programming, DP) 

동적계획법(Dynamic Programming, DP)

※ 아래층 이동은 현재 층에서 선택된 수에서 대각선 왼쪽 혹은 대각선 오른쪽 입니다.

arr[i][j] → arr[i+1][j] or arr[i+1][j+1]

[n = 1]

→ result = 7

 

[n = 2]

   7 - 3 = 10

   7 - 8 = 15

→ result = 15

 

[n = 3]

    7 - 3 - 8 = 18

    7 - 3 - 1 = 11

    7 - 8 - 1 = 16

    7 - 8 - 0 = 15

→ result = 18

 

▶ dp[i] = 해당 지점에 오르기까지 최대 점수

배열 구조상 n번째 층의 처음지점과 끝지점에는 내려가는 경로는 한가지씩만 존재

중간 부분에서는 위에서 두 방향에서 내려올 수 있습니다. 

---

import java.util.Scanner;
 
public class Main {
    public static void main(String[] args){
        Scanner sc = new Scanner(System.in);
         
        int n = Integer.parseInt(sc.nextLine());
        int[][] arr = new int[n][];
         
        // 배열 생성 및 값 할당(입력)
        for(int i=0; i<n; i++) {
            arr[i] = new int[i+1];
            for(int j=0; j<=i; j++) {
                arr[i][j] = Integer.parseInt(sc.next());
            }
        }
         
        int result = arr[0][0];
        // 입력받은 2차원 배열에서 각 층의 배열을 함수에 넘긴다.
        if(arr.length == 1) {
            System.out.println(result);
            return;
        }else {
                 
            // 최대 비용으로 가는 누적값들을 쌓아간다.
            for(int i=0; i<n-1; i++) {
                dynamicFunc(arr[i], arr[i+1]);    
            }
             
            result = arr[n-1][0];
             
            // 마지막 배열에서 가장 큰 값 도출.
            for(int i = 1; i < arr[n-1].length; i++) {
                if(arr[n-1][i] > result) {
                    result = arr[n-1][i];
                }
            }
            // 정답 출력
            System.out.println(result);
        }
    }
 
    private static void dynamicFunc(int[] before, int[] now){
         
        for(int i=0; i < now.length; i++) {
            if(i == 0) { 
                now[i] = now[i] + before[i];
            }
            else if(i == now.length -1) {
                now[i] = now[i] + before[i-1];
            }
            else {
                now[i] = now[i] + Math.max(before[i-1], before[i]);
            }    
        }
    }
}