[algospot] TRIPATHCNT

문제링크 입니다

[TRIPATHCNT] 문제 😄😄😄😄😄

9
5 7
1 3 2
3 5 5 6\

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

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

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

입력

입력의 첫 줄에는 테스트 케이스의 수 C(C <= 50)가 주어집니다. 각 테스트 케이스의 첫 줄에는 삼각형의 크기 n(2 <= n <= 100)이 주어지고, 그 후 n줄에는 각 1개~n개의 숫자로 삼각형 각 가로줄에 있는 숫자가 왼쪽부터 주어집니다. 각 숫자는 1 이상 100000 이하의 자연수입니다.

출력

각 테스트 케이스마다 한 줄에 최대 경로의 수를 출력합니다.
경로의 수는 230 이하라고 가정해도 좋습니다.

입력 예제

2
4
1
1 1
1 1 1
1 1 1 1
4
9
5 7
1 3 2
3 5 5 6

출력 예제

8
3

전체 코드는 다음과 같습니다.

//
//  TRIPATHCNT.cpp
//  AALGGO
//
//  Created by inhyeok on 2021/09/25.
//

#include <iostream>
#include <fstream>
#include <algorithm>
#include <cstring>
#include <vector>
using namespace std;
int n;
ifstream fin("TRIPATHCNT.txt");
int cache[100][100];
int arr[101][101];

int path2(int y, int x){
    if(y == n ) return 0;
    int &ret = cache[y][x];
    if(ret != -1) return ret;
    ret = arr[y][x];
    ret = ret + max(path2(y+1,x), path2(y+1, x+1));
    return ret;
}
int countcache[101][101];
int count(int y, int x){
    if(y == n-1 ) return 1;
    int &ret = countcache[y][x];
    if(ret != -1) return ret;
    ret = 0;
    if(path2(y+1, x+1) >= path2(y+1,x) ){
        ret = ret + count(y+1,x+1);
    }

    if(path2(y+1, x+1) <= path2(y+1,x) ){
        ret = ret + count(y+1,x);
    }

    return ret;
}

int main(int argc, const char * argv[]) {
    int Test_case;
    fin >> Test_case;

    for (int i=0; i< Test_case ; i++){
        fin >> n;
        memset(cache,-1,sizeof(cache));
        memset(arr,-1,sizeof(arr));
        memset(countcache,-1,sizeof(countcache));
        for (int j=0; j<n; j++){
            for(int k=0; k<=j; k++){
                fin >> arr[j][k];
            }
        }

        cout << count(0,0) << endl;
    }
    return 0;
}