lv3) 정수 삼각형

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

프로그래머스

 

#1 위->아래

#include <string>
#include <vector>

using namespace std;

int dp[501][501];
int solution(vector<vector<int>> triangle) {
    dp[0][0] = triangle[0][0];
    int n = triangle.size();
    for (int y = 0; y < n - 1; ++y) {
        for (int x = 0; x < triangle[y].size(); ++x) {
            dp[y + 1][x] = max(dp[y + 1][x], dp[y][x] + triangle[y + 1][x]);
            dp[y + 1][x + 1] = max(dp[y + 1][x + 1], dp[y][x] + triangle[y + 1][x + 1]);
        }
    }
    int maxi = -1;
    for (int x = 0; x < 501; ++x) {
        if (maxi < dp[n - 1][x]) {
            maxi = dp[n - 1][x];
        }
    }
    return maxi;
}

int main() {
    solution({ {7},{3,8},{8,1,0},{2,7,4,4} ,{4,5,2,6,5} });
}

 

#2 아래->위

#include <string>
#include <vector>

using namespace std;

int dp[501][501];
int solution(vector<vector<int>> triangle) {
    dp[0][0] = triangle[0][0];
    int n = triangle.size();
    for (int y = 1; y < n; ++y) {
        for (int x = 0; x < triangle[y].size()-1; ++x) {
            dp[y][x] = max(dp[y][x], dp[y-1][x] + triangle[y][x]);
            dp[y][x + 1] = max(dp[y][x + 1], dp[y-1][x] + triangle[y][x + 1]);
        }
    }
    int maxi = -1;
    for (int x = 0; x < 501; ++x) {
        if (maxi < dp[n - 1][x]) {
            maxi = dp[n - 1][x];
        }
    }
    return maxi;
}

int main() {
    solution({ {7},{3,8},{8,1,0},{2,7,4,4} ,{4,5,2,6,5} });
}