TRIANGLEPATH

TRIANGLEPATH

기본적인 DP 문제.

시간 복잡도는 한줄 밑으로 내려갈 때마다 2배씩 증가하므로 2^n-1 이 된다.

따라서 n의 최대값이 100이 시간 내에 구할 수 없게 되므로 DP 를 이용해야 한다.

cache[x][y] 는 x,y 에서 얻을 수 있는 최대 점수

cache[x][y] = map[x][y]        + max(cache[x+1][y] , cache[x+1][y+1])

현재 자신의 값 + MAX((x+1,y) 에서 얻을 수 있는 최대값 (x+1,y+1)에서 얻을 수 있는 최대값)

가 되므로 이를 재귀 함수를 이용해서 구현할 수 있다.

굳이 cache 값을 -1로 초기화 하지 않은 이유는, 조건에서 map에 들어가는 값은 1이상 이기 때문에

<정답 코드>

#include<iostream>
#include<algorithm>
using namespace std;
int n;
int map[101][101];
int cache[101][101];
 
int go(int x, int y)
{
    int &ret = cache[x][y];
    
    //기저 조건 : 맨 마지막 행에 도달했을 때
    if (x == n) {
 
        return map[x][y];
    }
 
    // 캐시 값이 존재할 때
    if (ret != 0)
    {
        return ret;
    }
 
    //최대값에 자신의 값을 더한 값
 
    ret += max(go(x + 1, y), go(x + 1, y + 1)) + map[x][y];
 
 
    return ret;
 
 
}
void init()
{
    for(int i=0;i<101;i++)
        for (int j = 0; j < 101; j++)
        {
            map[i][j] = 0;
            cache[i][j] = 0;
        }
}
int main()
{
    //freopen("input.txt", "r", stdin);
    int tc;
    cin >> tc;
    for (int t = 1; t <= tc; t++) {
        init();
        cin >> n;
        for (int i = 1; i <= n; i++) {
            for (int j = 1; j <= i; j++) {
                cin >> map[i][j];
            }
        }
 
        cout << go(0,0) << endl;
 
    }
 
    return 0;
}