[종만북] - 삼각형 위의 최대경로(DP)

문제

https://www.algospot.com/judge/problem/read/TRIANGLEPATH

algospot.com :: TRIANGLEPATH

접근방법

 메모이제이션을 활용한다.

중복 계산을 없앨 수 있다.

완전 탐색이라면 최악의 경우 2^100 을 훨씬 넘어가지만,

 

메모이제이션을 활용하면, 저장된 값을 재사용가능하기 때문에,

100 * 100 = 10000 의 계산 내에서 해결 가능하다.

 

코드

#include <iostream>
#include <vector>
#include <algorithm>
#include <string>
#include <cstring>

using namespace std;

#define FOR(i, n) for (int i=0;i<(n);++i)
#define INF 987654321

int n, triangle[100][100];
int cache2[100][100];

// (y, x)의 위치부터 맨 아래줄까지 내려가면서 얻을 수 있는 최대 경로의 합을 반환한다.
int path2(int y, int x) {
    //기저사례
    if (y == n-1) return triangle[y][x];
    //메모이제이션
    int& ret = cache2[y][x];
    if (ret != -1) return ret;
    return ret = max(path2(y+1, x+1), path2(y+1, x)) + triangle[y][x];
}

int C;

int main () {
    cin >> C;
    while(C--) {
        cin >> n;
        memset(cache2, -1, sizeof(cache2));
        memset(triangle, 0, sizeof(triangle));
        FOR(i, n) FOR(j, i+1) cin >> triangle[i][j];
        cout << path2(0, 0) << endl;
    }

    return 0;
}

개선할 점

 

<cstring> 헤더가 있어야 memset 함수를 사용할 수 있다.