TRIPATHCNT (중하, p. 254)

소요 시간: 15분

책 난이도는 ‘중’인데 ‘중하’로 하향 조정

mx값 구하는 DP방식에 cnt만 추가로 세어주면 됨.

f(0,0)을 call하면 v[0][0] 정점에 대한 mx값과 mx값이 나타나는 경로수 cnt를 같이 반환하도록 점화식 구성

#include <bits/stdc++.h>
using namespace std;
vector<vector<int>> v;
int n;
struct Info{
    int mx, cnt;
    Info() {}
    Info(int mx, int cnt):mx(mx),cnt(cnt) {}
};
Info info[101][101];
Info f(int x, int y) {
    if(y<0||y>=n) return Info(0,0);
    if(x==n-1) return Info(v[x][y],1);

    Info & ret = info[x][y];
    if(ret.mx) return ret;

    Info lhs = f(x+1,y);
    Info rhs = f(x+1,y+1);
    ret.mx = max(lhs.mx, rhs.mx) + v[x][y];
    if(lhs.mx > rhs.mx) ret.cnt=lhs.cnt;
    else if(lhs.mx < rhs.mx) ret.cnt=rhs.cnt;
    else ret.cnt=lhs.cnt+rhs.cnt;
    return ret;
}
int main() {
    ios::sync_with_stdio(false); cin.tie(0);
    int tc; cin >> tc;
    while(tc--) {
        cin >> n;
        
        v.clear(); v.resize(n, vector<int>());
        for(int i=0; i<n; i++) {
            v[i].clear(); v[i].resize(i+1);
            for(int j=0; j<=i; j++) {
                cin >> v[i][j];
            }
        }

        memset(info, 0, sizeof(info));
        Info ans = f(0,0);
        printf("%d\n", ans.cnt);
    }
    return 0;
}