문제
정수로 이루어진 삼각형의 꼭대기에서 아래쪽까지 경로를 따라 내려갈 때 거치는 수의 합의 최댓값을 구하는 문제다. i행의 j번째 칸에서는 i+1행의 j번째 또는 j+1번째 칸으로만 이동할 수 있다. 삼각형의 행 수 N은 최대 500이다.
입력
- 첫째 줄: 삼각형의 크기 N (1 ≤ N ≤ 500)
- 다음 N개의 줄: i번째 줄에 i개의 정수 (0 이상 9999 이하)
출력
경로 합의 최댓값을 출력한다.
예제
| 입력 | 출력 |
|---|---|
5 7 3 8 8 1 0 2 7 4 4 4 5 2 6 5 | 30 |
풀이
Bottom-Up 방식으로 삼각형의 맨 아랫줄부터 DP 값을 채우고, 재귀(Top-Down)로 꼭대기에서 아래로 내려가며 최댓값을 구한다. dp[N-1][i]를 마지막 행의 값으로 초기화한 후, 위로 올라가며 아래 두 칸 중 큰 값을 선택해 현재 칸의 합을 채운다.
- 삼각형 데이터를
map[N][N]에 입력받는다. dp[N-1][i] = map[N-1][i]로 마지막 행을 초기화한다.recur(0, 0)을 호출해 꼭대기(0행 0열)에서 시작하는 최대 합을 구한다.recur(n, s)는 n행 s열에서 아래로 내려갈 때의 최대 합을 반환한다.dp[n][s]가 null이면max(recur(n+1, s), recur(n+1, s+1)) + map[n][s]로 계산하여 저장한다.- 맨 아랫줄(n == N-1)에 도달하면
dp[n][s]를 그대로 반환한다.
핵심 아이디어: 각 칸에서 아래 두 경로 중 더 큰 합을 선택하는 방식으로, 한 번 계산된 값은 dp에 메모이제이션하여 중복 계산을 방지한다. Integer[][] 타입을 사용해 null로 미계산 상태를 표현하는 점이 특징이다.
코드
package com.ssafy.an.day099;
import java.io.BufferedReader;
import java.io.InputStreamReader;
import java.util.StringTokenizer;
public class Day67BOJ1932정수삼각형 { // 1932 정수 삼각형 DP
static int N, ans;
static int[][] map;
static Integer[][] dp; // 랩핑으로 선언하면 null객체로 관리할 수 있다.
public static void main(String[] args) throws Exception {
BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
StringTokenizer st = null;
N = Integer.parseInt(br.readLine());
ans = 1 << 22;
map = new int[N][N];
dp = new Integer[N][N];
for (int i = 0; i < N; i++) {
int j = 0;
st = new StringTokenizer(br.readLine());
while (st.hasMoreTokens()) {
map[i][j++] = Integer.parseInt(st.nextToken());
}
}
for (int i = 0; i < N; i++) // 아래서부터 큰값을 위층으로 넣는 방법
dp[N - 1][i] = map[N - 1][i];
ans = recur(0, 0); // 최종적으로 맨 윗층 첫번째 칸에 최대값이 저장됨
// print(dp);
System.out.println(ans);
br.close();
}
private static int recur(int n, int s) {
if (n == N - 1) return dp[n][s];
// print(dp);
return dp[n][s] = (dp[n][s] == null) ? M(recur(n + 1, s), recur(n + 1, s + 1)) + map[n][s] : dp[n][s];
}
private static int M(int a, int b) {
return Math.max(a, b);
}
private static void print(Integer[][] a) {
StringBuilder tt = new StringBuilder();
for (int i = 0; i < a.length; i++) {
for (int j = 0; j < a[i].length; j++) {
if(a[i][j]==null)
tt.append("n").append("\t");
else
tt.append(a[i][j]).append("\t");
}
tt.append("\n");
}
System.out.println(tt);
}
}복잡도
- 시간: O(N^2) — 삼각형의 총 칸 수는 N*(N+1)/2이며, 각 칸을 한 번씩 계산
- 공간: O(N^2) — dp 배열 N x N 크기