티스토리 뷰
https://algospot.com/judge/problem/read/TRIPATHCNT
algospot.com :: TRIPATHCNT
삼각형 위의 최대 경로 수 세기 문제 정보 문제 9 5 7 1 3 2 3 5 5 6 위 형태와 같이 삼각형 모양으로 배치된 자연수들이 있습니다. 맨 위의 숫자에서 시작해, 한 번에 한 칸씩 아래로 내려가 맨 아래
algospot.com
count(x,y) = (x,y)에서 시작해 맨 아래줄까지 내려가는 최대 경로의 수
#include <cstdio>
#include <cstring>
#include <algorithm>
using namespace std;
int n,triangle[100][100];
int cache[100][100],countCache[100][100];
int path(int x,int y)
{
if(x==n-1) return triangle[x][y];
int &ret=cache[x][y];
if(ret!=-1) return ret;
return ret=max(path(x+1,y),path(x+1,y+1))+triangle[x][y];
}
int count(int x,int y)
{
if(x==n-1) return 1;
int &ret=countCache[x][y];
if(ret!=-1) return ret;
ret=0;
if(path(x+1,y+1)>=path(x+1,y)) ret+=count(x+1,y+1);
if(path(x+1,y+1)<=path(x+1,y)) ret+=count(x+1,y);
return ret;
}
int main()
{
int t;
scanf("%d",&t);
while(t--)
{
scanf("%d",&n);
for(int i=0;i<n;i++)
for(int j=0;j<i+1;j++)
scanf("%d",&triangle[i][j]);
memset(cache,-1,sizeof(cache));
memset(countCache,-1,sizeof(countCache));
printf("%d\n",count(0,0));
}
return 0;
}