[C++]BOJ 2579 - 계단 오르기

n번째 계단 까지 얻을 수 있는 최대 점수를 구하기 위해 두 가지 경우를 살펴보겠다.

n-1번째 계단을 밟고 왔을 경우

---

이 경우는 주어진 조건에 의해 n-2계단을 밟으면 안되므로 무조건 n-3계단을 밟고 와야 한다.
따라서 n-3번째 계단 까지 얻을 수 있는 최대 점수 + n-1번 계단의 점수 + n번 계단의 점수가 n번째 계단까지 얻을 수 있는 최대 점수가 된다.

n-2번째 계단을 밟고 왔을 경우

---

위의 상황보단 간단하다.
n-2계단 전에 n-3계단을 밟고 와도 문제가 없고 n-4계단을 밟고 왔어도 조건에 어긋나지 않는다.
따라서 n-2번째 계단 까지 얻을 수 있는 최대 점수 + n번 계단의 점수가 n번째 계단까지 얻을 수 있는 최대 점수가 된다.

위 두 경우 중 더 큰 값이 정답이다.

#include <iostream>
#include <algorithm>
using namespace std;
int n, m, d[301], dp[301];
int main() {
	cin >> n;
	for(int i = 1; i <= n; i++)
		cin >> d[i];
	dp[1] = d[1];
	dp[2] = d[1] + d[2];
	for(int i = 3; i <= n; i++)
		dp[i] = max(d[i - 1] + dp[i - 3], dp[i - 2]) + d[i];
	cout << dp[n];
}