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

문제

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

풀이

규칙 도저히 모르겠어서 풀이 찾아봄

dp[1] = 1번째 계단
dp[2] = 1번째 계단 + 2번째 계단
dp[3] = (1번째 계단 + 3번째 계단) or (2번째 계단 + 3번째 계단)
:
dp[i] = (dp[i-2] + i번째 계단) or (dp[i-3] + i-1번째 계단 + i번째 계단)

코드

#include <iostream>
#include <algorithm>

using namespace std;

int main() {
	int N;
	int stairs[300];
	int dp[300];

	cin >> N;
	for (int i = 0; i < N; i++) {
		cin >> stairs[i];
	}

	dp[0] = stairs[0];
	dp[1] = stairs[0] + stairs[1];
	dp[2] = max(stairs[0] + stairs[2], stairs[1] + stairs[2]);
	for (int i = 3; i < N; i++) {
		dp[i] = max(dp[i-2] + stairs[i], dp[i-3] + stairs[i-1] + stairs[i]);
	}

	cout << dp[N - 1];

	return 0;
}