종만북 삼각형 최대 경로 (Triangle) C++ 풀이 (코드제공)

1. 문제 설정 확인

종만북 문제 링크 : TRIANGLE

정말 대표적인 DP문제다. 사실 설명할 필요도 없이 많은 분들이 설명해주시고 있기 때문에, 어떤 설명보단 코드를 보는게 나을 것이라고 생각한다.

가장 중요한점은, 우리는 최대값 하나만 찾는거지, 경로 (어떤 계단을 밟아 내려갔는지)를 찾는 것이 아니다. 따라서 아래에서부터 위로 더해나간 값들을 한 계단 위에서 계속해서 비교해나가면 결국 제일 위에서 최대값이 나오게 된다.

3. 해답 코드

#include <iostream>
#include <algorithm>
#include <string.h>
using namespace std;

const int MAX = 100;
int triangle[MAX][MAX];
int n;
int cache[MAX][MAX];

int path(int y, int x){
    if (y == n - 1)
        return triangle[y][x];
    int& ret = cache[y][x];
    if (ret != -1)
        return ret;
    return ret = max(path(y + 1, x), path(y + 1, x + 1)) + triangle[y][x]; // 부분 경로의 최대치를 구한다.
}
int main(){
    int C;
    cin >> C;
    while (C--){
        cin >> n;
        memset(cache, -1, sizeof(cache));
        for(int i=0; i< n; ++i)
            for (int j = 0; j <= i; ++j){
                cin >> triangle[i][j];
            }
        int result = path(0, 0);
        cout << result << endl;
    }
    return 0;
}

Source

• 종만북, 2022.07.22
• CLion