알고스팟: 삼각형 위의 최대 경로 개수 세기 (ID: TRIPATHCNT)

[문제 링크]

algospot.com :: TRIPATHCNT

---

알고리즘은 다음과 같다.

먼저, tri[Y][X] 좌표에서 시작했을 때 최대값을 memo[Y][X]배열에 메모라이징하는 함수를 수행한다.

 

그 다음 최대 경로의 개수를 카운팅하는 함수를 수행한다. memo[Y][X]에는 좌표가 가지는 최대값이 저장되므로 memo[0][0]을 시작으로 갈 수 있는 좌표인 memo[Y+1][X] 와 memo[Y+1][X+1] 을 비교하여

값이 같을 경우 두 개의 좌표를 시작으로 할 때 가질 수 있는 최대 경로 개수의 합을 cntmemo[Y][X]에 저장하고,

값이 다를 경우 더 큰 쪽의 좌표를 시작으로 할 때 가질 수 있는 최대 경로 개수를  cntmemo[Y][X]에 저장한다.

 

기저사례로 Y == n-1 일 때, 즉 맨 아래에 도달했을 때 1을 리턴하여 최대 경로 개수를 카운팅해주면 원하는 결과를 얻을 수 있다.

---

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

int n, tri[101][101], memo[101][101], cntmemo[101][101];

inline int max(const int a, const int b) { return a > b ? a : b; }

int Solution(int startY, int startX)
{
	if (startY == n) return 0;

	int& ret = memo[startY][startX];
	if (ret != -1) return ret;
	
	int val = tri[startY][startX];
	return ret = max(val + Solution(startY + 1, startX), val + Solution(startY + 1, startX + 1));
}

int CountPath(int startY, int startX)
{
	if (startY == n-1) return 1;

	int& ret = cntmemo[startY][startX];
	if (ret != -1) return ret;

	ret = 0;
	if (memo[startY + 1][startX] > memo[startY + 1][startX + 1])
		return ret += CountPath(startY + 1, startX);
	else if (memo[startY + 1][startX] < memo[startY + 1][startX + 1])
		return ret += CountPath(startY + 1, startX + 1);
	else
		return ret += CountPath(startY + 1, startX) + CountPath(startY + 1, startX + 1);
}

int main(void)
{
	int tc;
	cin >> tc;
	while (tc--)
	{
		memset(memo, -1, sizeof(memo));
		memset(cntmemo, -1, sizeof(cntmemo));
		cin >> n;
		for (int i = 0; i < n; i++)
			for (int j = 0; j < i + 1; j++)
				cin >> tri[i][j];

		Solution(0,0);
		cout << CountPath(0, 0) << endl;
	}

	return 0;
}

알고리즘 200일 프로젝트 - 55 day