[알고리즘 문제해결전략] TRIANGLEPATH - 삼각형 위의 최대 경로

[생각의 흐름]

1. 완전 탐색을 하게 되면 2^100이라 타임 아웃 발생

2. 동적계획법을 통해 캐싱 

3. 캐싱은 cache[Y][X][sum]을 먼저 생각했으나 sum의 경우 100000 * 100이 되어 메모리 초과발생

4. cache[Y][X]가 가능한지 고민 => Y, X일 때 최대값만 구하면 된다. => 아래(Y+1, X)와 오른쪽 아래(Y+1, X+1) 의 값 중 큰 값을 선택

 

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

#include <stdio.h>
#include <memory.h>
#include <algorithm>

using namespace std;

const int MAX_SIZE = 101;

int n;
int triangle[MAX_SIZE][MAX_SIZE];
int cache[MAX_SIZE][MAX_SIZE];

int sol(int currentY, int currentX)
{
    if(currentY == n)
        return 0;
    
    int &ret = cache[currentY][currentX];
    if(ret != -1)
        return ret;

    // 아래로 내려가는 경우와 오른쪽 아래로 내려가는 경우 중 최대 값을 취한다.
    ret = triangle[currentY][currentX] + max(sol(currentY+1, currentX), sol(currentY+1, currentX+1));
    // 최대값을 캐싱한다.
    
    return ret;
}

int main(void)
{
    int C;
    scanf("%d", &C);
    while (C--)
    {
        scanf("%d", &n);

        for (int i = 0; i < n; i++)
        {
            for (int j = 0; j < i + 1; j++)
            {
                scanf("%d", &triangle[i][j]);
            }
        }

        memset(cache, -1, sizeof(cache));
        printf("%d\n", sol(0,0));
    }

    return 0;
}