[백준 2579] 계단 오르기

분류 : dp

 

요구사항

조건에 따라 계단을 올랏을 경우, n번째 계단에서의 최댓값 구하기

 

풀이

dp로 풀이한다

점화식을 구하여 top-down 방식으로 푼다

func(num) = max(map[num-1] + func(num-3) , func(num-2) + map[num]);

 

현재 자리의 최대값은

현재값 + 이전 값 + -3까지의 최대값

or

현재값 + -2까지의 최대값이다

 

 

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

int d[330];
int map[330];
int n;
int func(int num) {
	if (num == 0)
		return 0;
	if (num < 0) return 0;
	if (num == 1) return map[1];
	
	int &ref = d[num];
	if (ref != -1) return ref;
	//int a = max(2, 3);
	return ref = max( (map[num - 1]+ func(num - 3)), func(num - 2)) + map[num];
}

int main() {
	scanf("%d", &n);
	for(int i = 1; i <= n; i++) {
		scanf("%d", &map[i]);
		d[i] = -1;
	}
	//d[1] = 10;
	
	cout << func(n) << endl;
}