[Algospot] TRIANGLEPATH 삼각형 위의 최대 경로

문제 링크 :  https://algospot.com/judge/problem/read/TRIANGLEPATH

동적계획법을 이용하여 풀이하였습니다. dp를 처음접하는데 좋은 문제라 생각되네요

#include <cstdio> #include <iostream> #include <algorithm> #include <string.h> #include <stack> #include <queue> #include <vector> #include <functional> #define MAX 100 #define INF 0x7fffffff using namespace std; int n, t[MAX][MAX]; int dp[MAX][MAX]; int solve(int y, int x) { if(y==n-1) return t[y][x]; int& ret=dp[y][x]; if(ret != -1) return ret; return ret = max(solve(y+1,x), solve(y+1,x+1)) + t[y][x]; } int main(void) { int height; scanf("%d",&n); while(n--) { memset(dp,-1,sizeof(dp)); scanf("%d",&height); for(int i=0;i<height;i++) for(int j=0;j<i+1;j++) scanf("%d",&t[i][j]); cout<<solve(0,0)<<endl; } return 0; }