Triangle_Path

문제는 되게 간단함.

그냥 밑으로가나 오른쪽 밑으로가나 해서

가장 큰 수의 합을 찾는 부분임.

그냥 딱 최대의 합만 구하는 부분은

int N;
vector<vector<int>> board;
vector<vector<int>> cache;

int path(int y, int x)
{
	// 기저사항
    if (y == N) return 0;
    
    // 캐시확인
    int& ret = cache[y][x];
    if (ret != -1) return ret;

    // 적용
    return ret = board[y][x] + max(path(y + 1, x), path(y + 1, x + 1));
}

return ret = board_TP[y][x] + max(path(y + 1, x), path(y + 1, x + 1)); 

return 부분 보기 어렵다면
어쩌구 이부분 보기 어렵다면

int path(int y, int x)
{
	// 기저사항
    if (y == N) return 0;
    
    // 캐시확인
    int& ret = cache[y][x];
    if (ret != -1) return ret;

    // 적용
    board[y][x] + path(y + 1, x); // 아래로 갈 경우
    board[y][x] + path(y + 1, x + 1) // 대각선 어래로 갈경우
    // 이거 둘중에 큰것을 ret에 넣어서 반환을 해야함.
    
    그래서 
    ret = board[y][x] + max(path(y + 1, x), path (y + 1, x + 1));
   	이렇게 되는 것임
    return ret;
}

경로까지 출력하는 부분은

int N;
vector<vector<int>> board_TP;
vector<vector<int>> cache_TP;
vector<vector<int>> nextX_TP;

int path(int y, int x)
{
    if (y == N) return 0;
    
    // 캐시확인
    int& ret = cache_TP[y][x];
    if (ret != -1) return ret;

    // 경로 기록
    {
        int nextBottom = path(y + 1, x);
        int nextBottomRight = path(y + 1, x + 1);
        if (nextBottom > nextBottomRight)
            nextX_TP[y][x] = x;
        else
            nextX_TP[y][x] = x + 1;
    }

    // 적용
    return ret = board_TP[y][x] + max(path(y + 1, x), path(y + 1, x + 1));

    return 1;
}


int main()
{
    board_TP = vector<vector<int>>
    {
        {6},
        {1, 2},
        {3, 7, 4},
        {9, 4, 1, 7},
        {2, 7, 5, 9, 4}
    };

    N = board_TP.size();
    cache_TP = vector<vector<int>>(N, vector<int>(N, -1));
    nextX_TP = vector<vector<int>>(N, vector<int>(N));

    int ret = path(0, 0);
    cout << ret << endl;


    // 경로 만들기
    int y = 0;
    int x = 0;

    while (y < N)
    {
        cout << board_TP[y][x] << " -> ";

        x = nextX_TP[y][x];
        ++y;
    }

    return 0;
}

이렇게 되겠다.