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

9

5 7

1 3 2

3 5 5 6

위 형태와 같이 삼각형 모양으로 배치된 자연수들이 있습니다. 맨 위의 숫자에서 시작해, 한 번에 한 칸씩 아래로 내려가 맨 아래 줄로 내려가는 경로를 만들려고 합니다. 경로는 아래 줄로 내려갈 때마다 바로 아래 숫자, 혹은 오른쪽 아래 숫자로 내려갈 수 있습니다.

이 때 숫자의 합이 가장 큰 경로는 하나가 아니라 여러 개일 수 있습니다. 예를 들어 위 삼각형에서는 {9, 7, 2, 6}과 {9, 7, 3, 5}의 합이 모두 최대인 24이고, {9, 7, 3, 5}는 두 번 등장하거든요.

삼각형이 주어질 때 최대 경로의 수를 세는 프로그램을 작성하세요.

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

#include<stdio.h>

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

using namespace std;

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

int path(int,int);
int count(int x,int y);
int main(){

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

 for(int c = 0 ; c < loop ; c++){

  memset(cache,0,sizeof(cache));
  memset(cnt,0,sizeof(cnt));
  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",count(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));
}
int count(int x,int y){
 if(x == n-1) return 1;
 if(cnt[x][y] != 0) return cnt[x][y];

 cnt[x][y] = 0;

 if(path(x+1,y+1) >= path(x+1,y))
  cnt[x][y] = cnt[x][y] + count(x+1,y+1);
 if(path(x+1,y+1) <= path(x+1,y))
  cnt[x][y] = cnt[x][y] + count(x+1,y);

 return cnt[x][y];

}