algospot TRIANGLEPATH 삼각형 위의 최대 경로

문제

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

걸린 시간

00 : 34 : 57 실패

풀이

C++

#include <stdio.h>
#include <iostream>
#include <string.h> // memset
using namespace std;

#define INF 987654321

int N;
int triangle[100][100];
int cache[100][100];

int solve(int r, int c){
    int ans = triangle[r][c];

    // 기저 사례 : 맨 아랫줄이면
    if(r == N-1) return ans;

    // 메모이제이션
    int& ret = cache[r][c];
    if(ret != -1) return ret;

    return ret = max(solve(r+1, c), solve(r+1, c+1))+ans;
}

int main(){
    int tc;
    scanf("%d", &tc);
    while(tc--){
        int count = 1;
        scanf("%d", &N);
        memset(triangle, 0, sizeof(triangle));
        memset(cache, -1, sizeof(cache));
        for(int r = 0; r < N; r++){
            for(int c = 0; c < count; c++){
                scanf("%d", &triangle[r][c]);
            }
            count++;
        }

        printf("%d\n", solve(0, 0));
    }
    return 0;
}

dp 문제인 것도 알았고, 메모이제이션을 사용해 반복을 줄여야 하는 것도 알았는데 어디서 중복이 일어나는지를 찾지 못했다.

피보나치 수열처럼 규칙적인 값들의 합이 아닌 특정 위치의 결과값을 메모이제이션에 사용하는 경우는 접하지 못했던 유형이라 순환호출 과정을 손으로 몇번 그려보고 나서야 이해를 했다.