repl.it
@TaeHunKim/

TRIPATHCOUNT

C++11

No description

fork
loading
Files
  • main.cpp
main.cpp
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
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
/*
https://algospot.com/judge/problem/read/TRIPATHCNT

문제

9
5 7
1 3 2
3 5 5 6

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

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

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

#include <iostream>
#include <vector>

using namespace std;

template <template <class...> class TT, class ...T>
ostream& operator<<(ostream& os, const TT<T...>& c)
{
    os << "{ ";
    for (const auto& x : c)
        os << x << " ";
    os << "}";
    return os;
}

int path2(int y, int x, int triangle[100][100], int countcache[100][100], int numRows)
{
       //base case
       if (y == numRows-1)
           return triangle[y][x];
       //memo
       int& ret = countcache[y][x];
       if (ret != -1)
           return ret;
       int leftCount = path2(y+1, x, triangle, countcache, numRows);
       int rightCount = path2(y+1, x+1, triangle, countcache, numRows);
       if (leftCount > rightCount)
        return ret =     
       
}

size_t count(const vector<int>& triangle)
{
    int vectorIdx = 0;
    int triangleHeight = 0;
    int triangleArr[100][100];
    for (triangleHeight = 0; vectorIdx < triangle.size(); triangleHeight++) {
        for (int j = 0; j < triangleHeight; j++) {
            triangleArr[triangleHeight][j] = triangle[vectorIdx];
            vectorIdx++;
        }
    }
    /*
    vectorIdx = 0;
    for (int i = 0; i < triangleHeight; i++) {
        for (int j = 0; j < i; j++) {
            cout << triangleArr[i][j] << " ";
        }
        cout << endl;
    }
    */
    
    int countcache[100][100];
    for(int i = 0; i < 100; i++)
        for (int j =0; j < 100; j++)
            countcache[i][j] = -1;
    
    return path2(0, 0, triangleArr, countcache, triangleHeight);
}

int main()
{
    vector<int> triangle1({1, 1,1, 1,1,1, 1,1,1,1});
    vector<int> triangle2({9, 5,7, 1,3,2, 3,5,5,6});
    vector<int> triangle3({6, 1,2, 3,7,4, 9,4,1,7});
    vector<int> triangle4({1, 2,4, 8,16,8, 32,64,32,64, 128,256,128,256,128});
    vector<int> triangle5({6, 1,2, 3,7,4, 9,4,1,7, 2,7,5,9,4});
    
    cout << count(triangle1) << endl;
    cout << count(triangle2) << endl;
    cout << count(triangle3) << endl;
    cout << count(triangle4) << endl;
    cout << count(triangle5) << endl;
}
Fetching token
?