삼각형 위의 최대 경로

문제 : https://algospot.com/judge/problem/read/TRIANGLEPATH

입력

입력의 첫 줄에는 테스트 케이스의 수 C(C <= 50)가 주어집니다. 각 테스트 케이스의 첫 줄에는 삼각형의 크기 n(2 <= n <= 100)이 주어지고, 그 후 n줄에는 각 1개~n개의 숫자로 삼각형 각 가로줄에 있는 숫자가 왼쪽부터 주어집니다. 각 숫자는 1 이상 100000 이하의 자연수입니다.

출력

각 테스트 케이스마다 한 줄에 최대 경로의 숫자 합을 출력합니다.

코드( C++ ) 종만북 참조

#include <iostream>

#include <algorithm>

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]; // 부분 경로의 최대치를 구한다.

}

void Init()

{

for (int i = 0; i < n; ++i)

for (int j = 0; j <= i; ++j)

cache[i][j] = -1;

}

int main()

{

int C;

cin >> C;

while (C--)

{

cin >> n;

Init();

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;

}