동적 계획법 - 9. 삼각형 위의 최대 경로 개수 세기

문제 : 삼각형 위의 최대 경로 개수 세기 (난이도 : 中)

 

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

 분석

이 문제는 앞서 푼 삼각형 위의 최대 경로 문제의 연장 문제이다.

2020/12/24 - [알고리즘 문제 해결 전략] - 동적 계획법 - 3. 삼각형 위의 최대 경로

동적 계획법 - 3. 삼각형 위의 최대 경로

 

최대 경로의 합을 반환하는 함수 path()가 있다고 하고, count(y, x) = (y, x)에서 시작해 맨 아래줄까지 내려가는 최대 경로의 수를 반환한다고 하자. 그럼 다음과 같은 식을 세울 수 있다.

 

count(y, x) = max {

(path(y+1, x) > path(y+1, x+1)) -> count(y+1, x),

(path(y+1, x) < path(y+1, x+1)) -> count(y+1, x+1),

(path(y+1, x) == path(y+1, x+1)) -> count(y+1, x) + count(y+1, x+1)

}

 

위 점화식을 구현할 때 조건식 3개가 아닌 2개로 구현하는 것에 유의하며 봐보자.

 

 구현

int n;
int cache[100][100], triangle[100][100];
//최대 합을 반환한다.
int path(int y, int x)
{
	//base case : 마지막 칸인 경우
	if (y == n - 1) return triangle[y][x];
	//memoizaiton
	int& ret = cache[y][x];
	if (ret != -1) return ret;
	return ret = max(path(y + 1, x), path(y + 1, x + 1)) + triangle[y][x];
}

int count_cache[100][100];
//최대 합의 경로 수를 반환한다.
int count(int y, int x)
{
	//base case : 마지막 칸인 경우
	if (y == n - 1) return 1;
	//memoization
	int& ret = count_cache[y][x];
	if (ret != -1) return ret;
	ret = 0; // 조건식 3개를 2개로 처리하는 과정. 
	if (path(y + 1, x) >= path(y + 1, x + 1)) ret += count(y + 1, x);
	if (path(y + 1, x) <= path(y + 1, x + 1)) ret += count(y + 1, x + 1);
	return ret;
}

int main()
{
	int c;
	cin >> c;
	while (c--)
	{
		memset(cache, -1, sizeof(cache));
		memset(count_cache, -1, sizeof(count_cache));
		cin >> n;
		for (int y = 0; y < n; y++)
		{
			for (int x = 0; x <= y; x++)
			{
				cin >> triangle[y][x];
			}
		}
		int ans = count(0, 0);
		cout << ans << '\n';
	}
	return 0;
}