알고스팟 - 삼각형 위의 최대 경로 개수 세기 (TRIPATHCNT) [C++]

 이 문제는 다이나믹 프로그래밍을 사용하여 최적해를 구한 뒤, 최적해로 다다르는 경로의 개수를 세는 문제이다. 이 문제에 대해 경로의 개수를 세는 부분이 어려웠는데, 앞서 구했던 dp 배열을 통해 구할 수 있다는 힌트를 얻었다. 바로 아래와 아래 오른쪽 둘 중 dp 배열의 값이 큰 쪽으로 재귀를 호출하며, 만약 같을 경우에는 둘 다 최적해 경로일 가능성이 있으므로 둘 다 호출한 뒤 더해주면 된다.

 

 이미 dp 배열을 사용하는데 왜 countDP가 따로 필요할 까 의문이 들었는데, 만약 삼각형의 모든 수가 같다면 재귀 호출을 매우 많이 하게 된다. 이를 방지하기 위해서는 coundDP가 또 필요하게 된다.

 

 

#include <iostream>
#include <algorithm>

using namespace std;

#define MAX 100

int n;
int triangle[MAX + 1][MAX + 1];
int dp[MAX + 1][MAX + 1];
int countDP[MAX + 1][MAX + 1];

int findMax(int depth, int index) {
	if (depth == n + 1) {
		return 0;
	}

	if (dp[depth][index] != -1) {
		return dp[depth][index];
	}

	int result = 0;

	result = max(findMax(depth + 1, index), findMax(depth + 1, index + 1)) + triangle[depth][index];

	return dp[depth][index] = result;
}

int findCount(int depth, int index) {
	if (depth == n) {
		return 1;
	}

	if (countDP[depth][index] != -1) {
		return countDP[depth][index];
	}

	int result = 0;
	if (dp[depth + 1][index] > dp[depth + 1][index + 1]) {
		result += findCount(depth + 1, index);
	}
	else if (dp[depth + 1][index] < dp[depth + 1][index + 1]) {
		result += findCount(depth + 1, index + 1);
	}
	else {
		result += findCount(depth + 1, index) + findCount(depth + 1, index + 1);
	}

	return countDP[depth][index] = result;
}

void init() {
	for (int y = 1; y <= n; y++) {
		for (int x = 1; x <= y; x++) {
			dp[y][x] = -1;
			countDP[y][x] = -1;
		}
	}
}

int main() {
	ios_base::sync_with_stdio(0);
	cin.tie(0);
	cout.tie(0);

	int C;
	cin >> C;

	for (int test = 0; test < C; test++) {
		cin >> n;
		for (int i = 1; i <= n; i++) {
			for (int j = 1; j <= i; j++) {
				cin >> triangle[i][j];
			}
		}
		init();
		int maxValue = findMax(1, 1);

		cout << findCount(1, 1) << '\n';
	}

	return 0;
}