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

문제 링크

---

1. 문제 풀이

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

---

2. 코드

1. 풀이 [Java]

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[][] map = 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++) {
                map[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]) + map[i][j];
            }
        }

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

        System.out.println(max);
    }
}

2. 풀이 [C++]

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

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

    int n;
    cin >> n;

    vector<vector<int>> v(n, vector<int>(n));
    for (int i = 0; i < n; i++) {
        for (int j = 0; j <= i; j++) {
            cin >> v[i][j];
        }
    }

    vector<vector<int>> dp(1 + n, vector<int>(1 + n));
    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]) + v[i - 1][j - 1];
        }
    }

    cout << *max_element(dp[n].begin(), dp[n].end());
}

---