[Programmers] (동적계획법(Dynamic Programming)) Lv 3. 정수 삼각형

https://school.programmers.co.kr/learn/courses/30/lessons/43105

프로그래머스

 

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

using namespace std;

int solution(vector<vector<int>> triangle) {
    //24.10.21
    vector<vector<int>> dp{ triangle.front() };
    dp.resize(triangle.size());

    for (int i = 1; i < triangle.size(); ++i)
    {
        dp[i].resize(triangle[i].size());
        dp[i][0] = dp[i - 1][0] + triangle[i][0];
        dp[i].back() = dp[i - 1].back() + triangle[i].back();

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

    return *max_element(dp.back().begin(), dp.back().end());
}

GitHub : https://github.com/developeSHG/Algorithm-Baekjoon_Programmers/commit/0588b145bad56a7d727e1738917bc52b326c365f

[level 3] Title: 정수 삼각형, Time: 0.65 ms, Memory: 8.55 MB -BaekjoonHub · developeSHG/Algorithm-Baekjoon_Programmers@058