[ALGOSPOT] TRIPATHCNT

algospot.com/judge/problem/read/TRIPATHCNT

algospot.com :: 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

 

TRIANGLEPATH 문제(damper.tistory.com/8)의 변형문제입니다.

1. TRIANGLEPATH문제에서는 최대값만 저장했다면, 이번엔 pair에 현재 최대값을 올 수 있는 경로의 수도 같이 저장해줍니다.

2. 맨 마지막 줄에서 최대값일때의 경로의 수를 모두 더해주면 됩니다.

 

 

#include <bits/stdc++.h>
using namespace std;
#define swap(a,b) (a)^=(b)^=(a)^=(b)
#define endl '\n'
typedef long long lld;
 
int main()
{
    ios_base::sync_with_stdio(NULL);
    cin.tie(NULL);
    cout.tie(NULL);
    int tc;
    cin>>tc;
    while(tc--)
    {
        int n;
        cin>>n;
        vector<vector<int>> v(n, vector<int> (n+1, 0));
        for(int i=0;i<n;i++)
            for(int j=0;j<=i;j++)
                cin>>v[i][j];
        vector<vector<pair<int, int>>> dp(n+1, vector<pair<int, int>> (n+1, {0, 0}));
        dp[0][0].first = 1;
        dp[0][0].second = v[0][0];
        for(int i=0;i<n-1;i++)
        {
            for(int j=0;j<=i;j++)
            {
                if(dp[i+1][j].second<dp[i][j].second+v[i+1][j])
                {
                    dp[i+1][j].first = dp[i][j].first;
                    dp[i+1][j].second = dp[i][j].second+v[i+1][j];
                }
                else if(dp[i+1][j].second==dp[i][j].second+v[i+1][j])
                    dp[i+1][j].first+=dp[i][j].first;
                if(dp[i+1][j+1].second<dp[i][j].second+v[i+1][j+1])
                {
                    dp[i+1][j+1].first = dp[i][j].first;
                    dp[i+1][j+1].second = dp[i][j].second+v[i+1][j+1];
                }
                else if(dp[i+1][j+1].second==dp[i][j].second+v[i+1][j+1])
                    dp[i+1][j+1].first+=dp[i][j].first;
            }
        }
        int mx = dp[n-1][0].second-1, cnt = 0;
        for(int i=0;i<n;i++)
        {
            if(mx<dp[n-1][i].second)
            {
                cnt = dp[n-1][i].first;
                mx = dp[n-1][i].second;
            }
            else if(mx==dp[n-1][i].second) cnt += dp[n-1][i].first;
        }
        cout<<cnt<<endl;
    }
    return 0;
}