백준 2579 계단오르기

다이나믹 프로그래밍 너무 어렵다..

 

이런 n번째 ~ 문제들은 점화식을 통해서 접근해보자.

 

이 문제는 현재 n번쨰 계단의 위치는 n-3번쨰까지의 합에서 n-1, n 계단을 합한 것 or n-2번째 계단까지의 합에서 n번쨰 계단을 합한 것중 최대값을 구하면 된다.

 

#include <stdio.h>
#include <stack>
#include <algorithm>
#include<iostream>
using namespace std;
int main() {
	int n, arr[305] = {}, dp[305] = {};
	scanf("%d", &n);
	for (int i = 1; i <= n; i++) {
		scanf("%d", &arr[i]);
	}
	dp[1] = arr[1];
	dp[2] = dp[1] + arr[2];

	for (int i = 3; i <= n; i++) {
		dp[i] = max(dp[i - 2] + arr[i], dp[i - 3] + arr[i] + arr[i - 1]);
	}
	printf("%d", dp[n]);


}