[Algospot] 삼각형 위의 최대 경로 수 세기 (문제 ID : TRIPATHCNT)

문제

9

5 7

1 3 2

3 5 5 6

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

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

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

 

입력

입력의 첫 줄에는 테스트 케이스의 수 C(C <= 50)가 주어집니다. 각 테스트 케이스의 첫 줄에는 삼각형의 크기 n(2 <= n <= 100)이 주어지고, 그 후 n줄에는 각 1개~n개의 숫자로 삼각형 각 가로줄에 있는 숫자가 왼쪽부터 주어집니다. 각 숫자는 1 이상 100000 이하의 자연수입니다.

 

출력

각 테스트 케이스마다 한 줄에 최대 경로의 수를 출력합니다.
경로의 수는 230 이하라고 가정해도 좋습니다.

---

전에 풀었던 삼각형 위의 최대 경로 찾기 문제의 활용 문제이다. 우선 path1 함수를 통해 최대 경로값을 계산한다. 그 후 path2 함수를 통해

최대 경로를 갖는 경로 개수를 계산한다. 만약 바로 아래칸의 dp값(path1의 결과값)과 오른쪽 아래칸의 dp값이 같다면 두 경로를 합하고 아니라면 더 큰 dp값을 갖는 경로의 개수를 저장하면 된다. 점화식만 제대로 세운다면 이해하고 풀기 힘들지 않다.

 

 

코드 원본 : https://github.com/chosh95/STUDY/blob/master/Algospot/TRIPATHCNT.cpp

chosh95/STUDY

C++ 코드

#include <iostream>
#include <cstring>
#include <algorithm>
using namespace std;
int C, N;
int p[101][101];
int dp[101][101];
int cnt[101][101];
void path1(int x, int y)
{
	int& res = dp[x][y];
	if (res != -1) return;
	if (x == N) {
		res = p[x][y];
		return;
	}
	path1(x + 1, y);
	path1(x + 1, y + 1);
	res = p[x][y] + max(dp[x + 1][y], dp[x + 1][y + 1]);
	return;
}

int path2(int x, int y)
{
	if (x == N) return 1;
	int& res = cnt[x][y];
	if (res != -1) return res;
	res = 0;
	if (dp[x+1][y] == dp[x+1][y+1]) {
		return res = path2(x + 1, y) + path2(x + 1, y + 1);
	}
	else if (dp[x + 1][y] > dp[x + 1][y + 1]) {
		return res = path2(x + 1, y);
	}
	else return res = path2(x + 1, y + 1);
}
int main()
{
	cin >> C;
	while (C--) {
		cin >> N;
		memset(p, -1, sizeof(p));
		memset(dp, -1, sizeof(dp));
		memset(cnt, -1, sizeof(cnt));
		for (int i = 1; i <= N; i++) 
			for (int j = 1; j <= i; j++) 
				cin >> p[i][j];
		path1(1, 1);
		cout << path2(1, 1) << endl;
	}
}