[백준 1932] 정수 삼각형

분류 : dp

 

요구사항

꼭대기에서 시작하여 끝까지 가는 경로 중 각 노드에 적힌 값이 최대인 값을 구하여라

 

풀이

dp를 사용하여 top-down형식으로 구하였다

점화식은

ref = map[floor][now] + max(func(floor - 1, now - 1), func(floor - 1, now));

 

현재 위치에서의 최대값은 (현재층 -1)층의 왼쪽, 오른쪽 중 최대값을 더한 값이다

 

#include <iostream>
#include <algorithm>
#include <math.h>
using namespace std;

int d[550][550];
int map[550][550];
int n;
int func(int floor, int now) {
	if (floor == 1) {
		return map[1][1];
	}
	//cout << floor << " " << now << endl;
	int& ref = d[floor][now];
	if (ref != -1) {
		return ref;
	}
	if (now == 1) {
		ref = map[floor][now] + func(floor - 1, now);
	}
	else if (now == floor) {
		ref = map[floor][now] + func(floor - 1, now - 1);
	}
	else
		ref = map[floor][now] + max(func(floor - 1, now - 1), func(floor - 1, now));
	return ref;
	
	
}
int main() {
	scanf("%d", &n);
	for (int i = 1; i <= n; i++) {
		for (int j = 1; j <= i; j++) {
			scanf("%d", &map[i][j]);
			d[i][j] = -1;
		}
	}
	int ans = 0;
	for (int i = 1; i <= n; i++) {
		ans = max(ans, func(n, i));
	//	cout << ans << endl;
	}
	cout << ans << endl;

}