계단 오르기 C++ - 백준 2579

https://www.acmicpc.net/problem/2579

이 문제는 점화식을 어떻게 세우는지가 관건인 문제였다.

i번째 계단에 이르게 되는 경우는 두가지가 있다.

i-3번째 계단까지의 최댓값 + i-1번째 계단 값
or
i-2번째의 계단까지의 최댓값
이다. 따라서 이 점화식을 코드로 구현하면 다음과 같다.

#include <bits/stdc++.h>
#define MAX 300+1
#define FASTIO ios_base :: sync_with_stdio(false); cin.tie(NULL);
using namespace std;

int dp[MAX];
int arr[MAX];
int n;

int main(){
	FASTIO
	cin >> n;
	for(int i=0;i<n;i++){
		cin >> arr[i];
	}
	dp[0]=arr[0];
	dp[1]=arr[0]+arr[1];
	dp[2]=max(arr[0],arr[1])+arr[2];
	for(int i=3;i<n;i++){
		dp[i]=max(dp[i-2],dp[i-3]+arr[i-1])+arr[i];
	}
	cout << dp[n-1];
}