[c언어/c++] 삼각형 위의 최대 경로 TRIANGLEPATH 동적계획법

6

1  2

3  7  4

9  4  1  7

2  7  5  9  4

위 형태와 같이 삼각형 모양으로 배치된 자연수들이 있습니다. 맨 위의 숫자에서 시작해, 한 번에 한 칸씩 아래로 내려가 맨 아래 줄로 내려가는 경로를 만들려고 합니다. 경로는 아래 줄로 내려갈 때마다 바로 아래 숫자, 혹은 오른쪽 아래 숫자로 내려갈 수 있습니다. 이 때 모든 경로 중 포함된 숫자의 최대 합을 찾는 프로그램을 작성하세요.

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

#include<stdio.h>

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

using namespace std;

int n;
int tri[101][101];
int cache[101][101];

int path(int,int);

int main(){

 int loop;
 scanf("%d",&loop);

 for(int c = 0 ; c < loop ; c++){
  memset(cache,0,sizeof(cache));
  scanf(" %d",&n);
  for(int i = 0 ; i < n ; i++){
   for(int j = 0 ; j < i+1 ;j++){
    scanf(" %d",&tri[i][j]);
   }
  }

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

 return 0;

}
int path(int x,int y){
 if(x > n-1) return cache[x][y];
 if(cache[x][y] != 0) return cache[x][y];
 return cache[x][y] = tri[x][y] + max(path(x+1,y), path(x+1,y+1));
}