8장 동적계획법 2

8.4 전통적 최적화 문제들

예제: 삼각형 위의 최대 경로(문제ID: TRIANGLEPATH, 난이도: 하)

문제 자세히 보기

#include <iostream>
#include <vector>
#include <algorithm>

using namespace std;

int maxPath(vector< vector<int> > triangle) {
    int n = triangle.size();
    vector< vector<int> > path(n, vector<int>(n, 0));

    for(int i = 1; i < n; ++i) {
        for(int j = 1; j <= i; ++j) {
            path[i][j] = triangle[i][j] + max(path[i-1][j], [i-1][j-1]);
        }
    }

    int maxVal = 0;
    for(int i = 1; i < n; ++i)
        maxVal = max(maxVal, path[n-1][i]);

    return maxVal;
}

int main() {
    ios_base::sync_with_stdio(false);
    int C;
    cin >> C;
    while(C--) {
        int N;
        cin >> N;
        N++;
        vector< vector<int> > triangle(N, vector<int>(N, 0));
        for(int i = 1; i < N; ++i)
            for(int j = 1; j <= i; ++j)
                cin >> triangle[i][j];

        cout << maxPath(triangle) << endl;
    }
    
    return 0;
}

#include <iostream>
#include <cstring>
#include <algorithm>

using namespace std;

int N;
int triangle[100][100];
int path[100][100];
int maxPath(int y, int x) {
    if(y == N-1) return triangle[y][x];

    int& maxVal = path[y][x];
    if(maxVal != -1) return maxVal;

    return maxVal = triangle[y][x] + max(maxPath(y+1, x), maxPath(y+1, x+1));
}

int main() {
    ios_base::sync_with_stdio(false);
    int C;
    cin >> C;
    while(C--) {
        memset(path, -1, sizeof(path));
        cin >> N;

        for(int i = 0; i < N; ++i)
            for(int j = 0; j <= i; ++j)
                cin >> triangle[i][j];

        cout << maxPath(0, 0) << endl;
    }

    return 0;
}

Back to top ↑