알고스팟 - 삼각형 위의 최대 경로 (TRIANGLEPATH) [C++]

 이 문제는 다이나믹 프로그래밍으로 풀 수 있는 문제이다. 완전 탐색으로는 2^100 이므로 시간 초과가 나지만, 메모이제이션을 통해 O(n^2) 으로 만들 수 있다. n의 최댓값이 100이므로 충분히 시간 안에 풀 수 있다.

 

#include <iostream>
#include <algorithm>

using namespace std;

#define MAX 100

int n;
int triangle[MAX + 1][MAX + 1];
int dp[MAX + 1][MAX + 1];

int solve(int depth, int index) {
	if (depth == n + 1) {
		return 0;
	}

	if (dp[depth][index] != -1) {
		return dp[depth][index];
	}

	// straight
	int result = 0;

	result = max(result, solve(depth + 1, index) + triangle[depth][index]);
	result = max(result, solve(depth + 1, index + 1) + triangle[depth][index]);

	return dp[depth][index] = result;
}

void init() {
	for (int y = 1; y <= n; y++) {
		for (int x = 1; x <= n; x++) {
			dp[y][x] = -1;
		}
	}
}

int main() {
	ios_base::sync_with_stdio(0);
	cin.tie(0);
	cout.tie(0);

	int C;
	cin >> C;

	for (int test = 0; test < C; test++) {
		cin >> n;

		init();
		for (int y = 1; y <= n; y++) {
			for (int x = 1; x <= y; x++) {
				cin >> triangle[y][x];
			}
		}

		int answer = solve(1, 1);
		cout << answer << '\n';
	}

	return 0;
}