[백준저지] 1932번 : 정수 삼각형

www.acmicpc.net/problem/1932

1. 문제

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

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

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

2. 풀이

import java.util.*;

public class Main {
    public static void main(String args[]) {
        Scanner sc = new Scanner(System.in);
        int N = sc.nextInt();
        int[][] D = new int[N+1][N+1];
        int[][] A = new int[N+1][N+1];
        // 1 ~ N까지
        for (int i = 1; i <= N; i++) {
            // 1 ~ i까지
            for (int j = 1; j <= i; j++) {
                A[i][j] = sc.nextInt();
            }
        }
        
        for (int i = 1; i <= N; i++) {
            for (int j = 1; j <= i; j++) {
                if (D[i-1][j] > D[i-1][j-1]) {
                    D[i][j] = D[i-1][j] + A[i][j];
                } else {
                    D[i][j] = D[i-1][j-1] + A[i][j];
                }
            }
        }
        
        int result = Integer.MIN_VALUE;
        for (int i = 1; i <= N; i++) {
            if (D[N][i] > result) {
                result = D[N][i];
            }
        }
        System.out.println(result);
    }
}

D[i][j] => i행 j열이 선택되었을 때, 최대 합.

어떤 수가 선택되기 전에 선택된 수는 대각선 왼쪽 위 or 오른쪽 위에 있는 것.

(i, j)가 선택되기 전에 선택된 수는 (i-1, j), (i-1, j-1) 중 하나다.

D[i][j] = max(D[i-1][j], D[i-1][j-1]) + A[i][j]

 

위 점화식을 이용해서 해결.