정수삼각형 - 백준 1932

Info

실버 1, 다이나믹 프로그래밍

---

Solution

#include <iostream>
#include <vector>

using namespace std;
int n;
vector<vector<int>> triangle;
vector<vector<int>> maxTriangle;
int findMax(int depth, int OrderNumber) {
    if (n == 1) {
        return triangle[0][0];
    }
    if (n == 2) {
        return triangle[0][0] + max(triangle[1][0], triangle[1][1]);
    }
        if (depth == n - 2) {
            return triangle[depth][OrderNumber]
                + max(triangle[depth + 1][OrderNumber],
                    triangle[depth + 1][OrderNumber + 1]);
        }
        int left = 0;
        int right = 0;
        if (maxTriangle[depth+1][OrderNumber] != -1) {
            left = maxTriangle[depth + 1][OrderNumber];
        }
        else {
            left = findMax(depth + 1, OrderNumber);
        }
        if (maxTriangle[depth + 1][OrderNumber+1] != -1) {
            right = maxTriangle[depth + 1][OrderNumber + 1];
        }
        else {
            right = findMax(depth + 1, OrderNumber + 1);
        }

        int TriangleMax = triangle[depth][OrderNumber]
            + max(left, right);
        maxTriangle[depth][OrderNumber] = TriangleMax;
        return TriangleMax;
}
int main()
{
    cin >> n;
   
    //input
    for (int depth = 0; depth < n; depth++) {
        vector<int> line;
        vector<int> maxLine;
        for (int length = 0; length < (depth + 1); length++) {
            int tmp;
            cin >> tmp;
            line.push_back(tmp);
            maxLine.push_back(-1);
        }
        maxTriangle.push_back(maxLine);
        triangle.push_back(line);
    }
    cout << findMax(0,0);


}