[Programmers] 43105번 - 정수 삼각형 [Java][C++]

문제 링크

---

1. 문제 풀이

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

---

2. 코드

1. 풀이 [Java]

class Solution {
    public int solution(int[][] triangle) {
        int len = triangle.length;

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

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


        return ans;
    }
}

2. 풀이 [C++]

#include <algorithm>
#include <string>
#include <vector>

using namespace std;

int solution(vector<vector<int>> triangle) {
    int len = triangle.size();

    vector<vector<int>> dp(1 + len, vector<int>(1 + len));
    for (int i = 1; i <= len; i++) {
        for (int j = 1; j <= i; j++) {
            dp[i][j] = max(dp[i - 1][j - 1], dp[i - 1][j]) + triangle[i - 1][j - 1];
        }
    }

    return *max_element(dp[len].begin(), dp[len].end());
}

---