삼각형 위의 최대 경로(TRIANGLEPATH) 정답 코드

문제를 보시려면 여기를 클릭

이하는 코드입니다.

#include <string.h>
#include <stdio.h>
 
#pragma warning(disable:4996)
 
#define MAX(a, b) ((a) > (b) ? (a) : (b))
 
int board[101][101];
int cache[101][101];
 
int n;
 
int getSum(int y, int x) {
    if (y >= n - 1) {
        return board[y][x];
    }
 
    int& ret = cache[y][x];
    if (ret != -1) {
        return ret;
    }
 
    return ret = (board[y][x] + MAX(getSum(y + 1, x), getSum(y + 1, x + 1)));
}
 
int main() {
    int C;
    scanf("%d", &C);
 
    for (int i = 0; i < C; i++) {
        scanf("%d", &n);
 
        for (int j = 0; j < n; j++) {
            for (int k = 0; k <= j; k++) {
                scanf("%d", &board[j][k]);
            }
        }
 
        memset(cache, -1, sizeof(cache));
        printf("%d\n", getSum(0, 0));
    }
 
    return 0;
}