Algorithm/알고스팟

algospot - tripathcnt

jhg0406 2020. 2. 3. 15:12
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
//algospot - tripathcnt
 
#include <iostream>
#include <vector>
using namespace std;
 
int N;
vector<vector<int>> tri;
vector<vector<int>> cache;
vector<vector<int>> cache2;
 
void init()
{
    cin >> N;
    tri = vector<vector<int>>(N, vector<int>(N));
    cache2 = cache = vector<vector<int>>(N, vector<int>(N, -1));
    for(int i = 0; i<N; ++i)
        for(int j = 0; j<=i; ++j)
            cin >> tri[i][j];
}
 
int dp(int x, int y)
{
    if(x == N)
        return 0;
    int& ret = cache[x][y];
    if(ret != -1)
        return ret;
    ret = dp(x+1, y);
    ret = max(ret, dp(x+1, y+1));
    ret += tri[x][y];
    return ret;
}
 
int dp2(int x, int y)
{
    if(x == N-1)
        return 1;
    int& ret = cache2[x][y];
    if(ret != -1)
        return ret;
    ret = 0;
    if(cache[x+1][y] + tri[x][y] == cache[x][y])
        ret += dp2(x+1, y);
    if(cache[x+1][y+1] + tri[x][y] == cache[x][y])
        ret += dp2(x+1, y+1);
    return ret;
}
 
int main()
{
    int C; cin >> C;
    for(int tn = 0; tn<C; ++tn)
    {
        init();
        int max = dp(0,0);
        cout << dp2(0,0) << "\n";
    }
}
 cs

 

 

 

 

 

https://www.algospot.com/judge/problem/read/TRIPATHCNT

 

algospot.com :: TRIPATHCNT

삼각형 위의 최대 경로 수 세기 문제 정보 문제 9 5 7 1 3 2 3 5 5 6 위 형태와 같이 삼각형 모양으로 배치된 자연수들이 있습니다. 맨 위의 숫자에서 시작해, 한 번에 한 칸씩 아래로 내려가 맨 아래 줄로 내려가는 경로를 만들려고 합니다. 경로는 아래 줄로 내려갈 때마다 바로 아래 숫자, 혹은 오른쪽 아래 숫자로 내려갈 수 있습니다. 이 때 숫자의 합이 가장 큰 경로는 하나가 아니라 여러 개일 수 있습니다. 예를 들어 위 삼각형에서는 {9,

www.algospot.com

 

 

 

 

 

TRIPATHCNT

경우의 수 DP문제

삼각형 위의 최대 경로를 DP로 구한다음 경로를 찾기 위해 DP를 한번 더 사용하면 됩니다!