<종만북> 08. 동적계획법_삼각형 위의 최대 경로 개수 세기 (Tripath Count) c++

먼저 삼각형 위의 최대 경로 개수를 세기 위해서는 최대 경로를 푸는 알고리즘을 먼저 짜야한다.

(y,x) 의 위치에서 바로 아래 숫자 혹은 오른쪽 아래 숫자로 내려갈 수 있기 때문에 (y+1, x)와 (y+1, x+1) 중에 큰 숫자를 찾아 더해서 내려가면 된다.

연산을 수행하고 나면 (b)와 같은 결과를 얻을 수 있다.

여기서 최대 경로의 개수는 9-7-3-5, 9-7-3-5, 9-7-2-6 총 3개가 나온다.

(0,0)에서 시작 하는 최대 경로는 (1,0)과 (1,1)중 어느 쪽으로 내려가야 할지를 쉽게 알 수 있다
path2(1,1)> path2(1,0) 이기 때문에 항상 (1,1)로 내려가는 것이 이득이다. 따라서 (0,0)에서 시작하는 최대 경로의 개수는 항상 (1,1)에서 시작하는 최대 경로의 개수와 같다.

(1,1)에서는 내려갈 수 있는 두 칸에서 만들 수 있는 최대 경로의 합이 같기 때문에 어느 쪽으로 내려가도 최대 경로를 만들 수 있다.
따라서 두 위치에서 시작하는 최단 경로의 갯수를 더한 것이 (1,1)에서 시작하는 최대 경로의 개수가 된다.

count(y,x)=(y,x)에서 시작해 맨 아래줄까지 내려가는 최대 경로의 수 일 때 이와 같은 점화식을 만들 수 있다.

#include<iostream>
#include<algorithm>
using namespace std;

int n, triangle[100][100];
int cache[100][100];
int countCache[100][100];

int path2(int y, int x) {
	if (y == n - 1) return triangle[y][x];

	int& ret = cache[y][x];
	if (ret != -1) return ret;

	return ret = max(path2(y + 1, x), path2(y + 1, x + 1)) + triangle[y][x];
}

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 += count(y + 1, x + 1);
	if (path2(y + 1, x + 1) <= path2(y + 1, x)) ret += count(y + 1, x);

	return ret;
}

void init() {
	for (int i = 0; i < n; i++) {
		for (int j = 0; j < n; j++) {
			//triangle[i][j] = 0;
			cache[i][j] = -1;
			countCache[i][j] = -1;
		}
	}
}
int main() {

	int tCase;
	cin >> tCase;
	while (tCase--) {
		cin >> n;
		init();
		for (int i = 0; i < n; i++) {
			for (int j = 0; j <= i; j++) {
				cin >> triangle[i][j];
			}
		}
		cout << count(0, 0) << "\n";
	}

	return 0;
}