[백준 2579] 계단 오르기

제한이 있는 dp는

dp를 점화식으로 계산할때 if로 조건에 맞게 dp값을 찾아주려고 하면 안된다

 

이 문제는 3개의 계단을 연속으로 오르면 안된다는 조건을 가지고 있는데

이걸 현재 3개를 연속으로 올랐을때랑 안올랐을때를 if문에 넣어서 각 dp값을 구하려고 하면 안됨

 

그냥 3개 올라갈 수 없다는걸 납득하고

이에 맞는 점화식을 구해주면 됨

 

dp[0] dp[1] dp[2] 는 이미 값이 정해져 있으므로

dp 돌기전에 미리 초기화 해주고 3부터 계산해주면 됨

 

 

그리고 마지막 계단은 무조건 밟아야한다 했으므로

마지막 계단일때의 dp 값을 찾아주면 된다.

 

---

#include <iostream>
#define SIZE 301
using namespace std;

int main() {
	ios::sync_with_stdio(0);
	cin.tie(0); cout.tie(0);
	
	int stairs[SIZE] = { 0, }, dp[SIZE];
	int N; cin >> N;
	for (int i = 1; i <= N; i++) cin >> stairs[i];

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

	cout << dp[N];
	return 0;
}