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

문제 링크

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

algospot.com :: TRIANGLEPATH

 

삼각형 가장 위쪽의 위치에서 최대경로는

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 = 101;
	int arr[MAX][MAX];
	int d[MAX][MAX];
	int n;
	int dp(int x, int y){
	if (y == n)
	return arr[y][x];
	if (d[y][x] != -1)
	return d[y][x];
	return d[y][x] = arr[y][x] + max(dp(x, y+1), dp(x+1, y+1));
	}
	int main(){
	fastio;
	int _;
	cin >> _;
	while (_--){
	memset(d, -1, sizeof(d));
	cin >> n;
	for (int i=1;i<=n;i++)
	for (int j=1;j<=i;j++)
	cin >> arr[i][j];
	cout << dp(1, 1) << endl;
	}
	return 0;
	}

view raw trianglepath.cpp hosted with ❤ by GitHub