[BaekJoon] #1932 - 정수 삼각형 [Java][C++]

문제 링크

---

1. 아이디어

정수 삼각형에서 특정 위치까지 내려왔을 때 선택된 수의 합의 최댓값은 바로 위층의 왼쪽 대각선까지 올 때 선택할 수 있었던 수의 합과 오른쪽 대각선까지 올 때 선택할 수 있었던 수의 합 중 더 큰 값에 현재 위치의 수를 더하면 된다. 양 끝 칸은 윗층에서 올 수 있는 대각선이 하나뿐이지만 수가 모두 0 이상이므로 없는 쪽을 0으로 두어도 결과가 같다. 따라서 다이나믹 프로그래밍을 활용해 해결할 수 있다. 가장 마지막 층에서 어떤 칸이 최댓값인지 알 수 없으므로 한 번 쭉 탐색하며 최댓값을 찾으면 된다.

---

2. 복잡도

접근	시간	공간
풀이	$O(N^2)$	$O(N^2)$

($N$ = 입력값 n)

---

3. 코드

풀이 [Java][C++]

import java.io.*;
import java.util.*;

public class Main {
    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        StringTokenizer st;

        int n = Integer.parseInt(br.readLine());

        int[][] arr = new int[1 + n][1 + n];
        for (int i = 1; i <= n; i++) {
            st = new StringTokenizer(br.readLine());
            for (int j = 1; j <= i; j++) {
                arr[i][j] = Integer.parseInt(st.nextToken());
            }
        }

        int[][] dp = new int[1 + n][1 + n];
        for (int i = 1; i <= n; i++) {
            for (int j = 1; j <= i; j++) {
                dp[i][j] = Math.max(dp[i - 1][j - 1], dp[i - 1][j]) + arr[i][j];
            }
        }

        int max = 0;
        for (int i = 1; i <= n; i++) {
            max = Math.max(max, dp[n][i]);
        }

        System.out.println(max);
    }
}

#include <bits/stdc++.h>
using namespace std;

int arr[1 + 500][1 + 500];
int dp[1 + 500][1 + 500];

int main() {
    ios::sync_with_stdio(0);
    cin.tie(0);

    int n;
    cin >> n;

    for (int i = 1; i <= n; i++) {
        for (int j = 1; j <= i; j++) {
            cin >> arr[i][j];
        }
    }

    for (int i = 1; i <= n; i++) {
        for (int j = 1; j <= i; j++) {
            dp[i][j] = max(dp[i - 1][j - 1], dp[i - 1][j]) + arr[i][j];
        }
    }

    int mx = 0;
    for (int i = 1; i <= n; i++) {
        mx = max(mx, dp[n][i]);
    }

    cout << mx;
}

---