[Baekjoon] 1932번 : 정수 삼각형

1. 문제

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

• DP 문제

// 문제
        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번째 줄까지 정수 삼각형이 주어진다.

// 출력
첫째 줄에 합이 최대가 되는 경로에 있는 수의 합을 출력한다.

// 예제 입력 1
5
7
3 8
8 1 0
2 7 4 4
4 5 2 6 5

// 예제 출력 1
30

2. 핵심 아이디어

• 제일 마지막 줄에서 가장 큰 값이 최댓값
• DP로 해결

3. Python 문제풀이

import sys
input = sys.stdin.readline

n = int(input())
a = [[0 for _ in range(n + 1)] for i in range(n + 1)]
# dp[i][j] : i, j 도착했을 때의 최댓값
# dp[i][j] = max(dp[i-1][j-1], dp[i-1][j]) + a[i][j]
dp = [[0 for _ in range(n + 1)] for i in range(n + 1)]

for i in range(1, n + 1) :
  tmp = list(map(int, input().split()))
  for j in range(1, i + 1) :
    a[i][j] = tmp[j - 1]

for i in range(1, n + 1) :
  for j in range(1, i + 1) :
    dp[i][j] = max(dp[i - 1][j - 1], dp[i-1][j]) + a[i][j]

print(max(dp[-1]))

4. Java 문제풀이

import java.io.BufferedReader;
import java.io.InputStreamReader;
import java.io.IOException;
import java.util.StringTokenizer;

public class Main {
	static int[][] a;
	static Integer[][] dp;
	static int n;

	public static void main(String[] args) throws IOException {
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		n = Integer.parseInt(br.readLine());
		a = new int[n][n];
		dp = new Integer[n][n];
		StringTokenizer st;

		for (int i=0; i<n; i++) {
			st = new StringTokenizer(br.readLine(), " ");
			for (int j=0; j<i+1; j++) {
				a[i][j] = Integer.parseInt(st.nextToken());
			}
		}
		for (int i=0; i<n; i++) {
			dp[n-1][i] = a[n-1][i];
		}
		System.out.println(find(0, 0));
	}

	static int find(int depth, int idx) {
		if (depth == n - 1) return dp[depth][idx];
		if (dp[depth][idx] == null) {
			dp[depth][idx] = Math.max(find(depth + 1, idx), find(depth + 1, idx + 1)) + a[depth][idx];
		}
		return dp[depth][idx];

	}
}