백준 1932 / 정수 삼각형

문제

풀이

설명

아래층으로 내려올 때는 대각선 왼쪽 또는 대각선 오른쪽에 있는 것만 선택할 수 있다.
• A에서 선택할 수 있는 수: B, C
• B에서 선택할 수 있는 수: D, E
• C에서 선택할 수 있는 수: E, F

반대로 생각하면 어떤 수가 선택되기 전에 선택된 수는 대각선 왼쪽 위, 오른쪽 위에 있는 것이다.
• B에 오기 전: A
• C에 오기 전: A
• D에 오기 전: B
• E에 오기 전: B, C
• F에 오기 전: C

즉, 그림으로
다음과 같이 표현할 수 있다.

D[i][j] = i행 j열이 선택되었을 때, 최대합
(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]

코드

import java.util.Scanner;

public class Num1932 {

	public static void main(String[] args) {
		
		Scanner sc = new Scanner(System.in);
		
        int n = sc.nextInt();
        int[][] a = new int[n][n];
        int[][] d = new int[n][n];
        
        for (int i=0; i<n; i++) {
            for (int j=0; j<=i; j++) {
                a[i][j] = sc.nextInt();
            }
        }
        
        d[0][0] = a[0][0];
        
        for (int i=1; i<n; i++) {
            for (int j=0; j<=i; j++) {
                d[i][j] = d[i-1][j] + a[i][j];
                if (j-1 >= 0 && d[i][j] < d[i-1][j-1] + a[i][j]) {
                    d[i][j] = d[i-1][j-1] + a[i][j];
                }
            }
        }
        
        int ans = d[n-1][0];
        
        for (int i=0; i<n; i++) {
            if (ans < d[n-1][i]) {
                ans = d[n-1][i];
            }
        }
        
        System.out.println(ans);
	}
}

코드설명

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