[C++] 알고스팟/동적계획법 - 삼각형 위의 최대 경로 수 세기

문제 링크

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

algospot.com :: TRIPATHCNT

 

이전의 삼각형 위의 최대 경로 문제에서 연장되는 문제입니다.

이전 문제로 각 위치에서의 최대 경로를 아래 오른쪽과 같이 구할 수 있습니다.

 

 

이렇게 구하고난 경로 값을 이용해서

1. 현재 위치에서 한칸 아래  위치

2. 현재 위치에서 오른쪽 한칸 아래 위치

두 값중 더 큰쪽이 항상 최대 경로가 됩니다.

이 때 두 값이 동일하다면 두 곳 모두 최대 경로가 될 수 있습니다.

 

최대 경로를 찾으면 카운트를 해주고 그 아래 값에 대한 최대 경로를 재귀함수로 구해서 더해주면 됩니다.

 

구현 코드

 

	#include <iostream>
	#include <algorithm>
	#include <cstring>
	#define endl '\n'
	#define fastio cin.sync_with_stdio(false); cin.tie(nullptr)
	using namespace std;
	const int MAX = 100;
	int triangle[MAX][MAX];
	int cache[MAX][MAX];
	int countCache[MAX][MAX];
	int n;
	//각 위치에서의 최대 경로를 구한다.
	int path(int y, int x){
	if (y == n-1) return triangle[y][x];
	int &ret = cache[y][x];
	if (ret != -1) return ret;
	return ret = triangle[y][x] + max(path(y+1, x), path(y+1, x+1));
	}
	//최대경로의 개수를 구한다.
	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(path(y+1, x+1) >= path(y+1, x)) ret += count(y+1, x+1);
	if(path(y+1, x+1) <= path(y+1, x)) ret += count(y+1, x);
	return ret;
	}
	int main(){
	fastio;
	int _;
	cin >> _;
	while (_--){
	memset(cache, -1, sizeof(cache));
	memset(countCache, -1, sizeof(countCache));
	cin >> n;
	for (int i=0;i<n;i++)
	for (int j=0;j<=i;j++)
	cin >> triangle[i][j];
	cout << count(0, 0) << endl;
	}
	return 0;
	}

view raw tripathcnt.cpp hosted with ❤ by GitHub