[백준알고리즘] 2579번 계단오르기

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

두 칸 이상 건너뛸 수 없는 조건 때문에 생각이 안나서 오래 걸렸다 ㅠㅠ

#include<iostream>
using namespace std;
#define max(a,b) ((a) > (b)) ? (a) :(b) 
 
int dp[302];
int step[302];
 
int main(void)
{
    int n;
    cin >> n;
 
    for (int i = 1; i <= n; i++)
    {
        cin >> step[i];
    }
 
    dp[1] = step[1];
    dp[2] = step[1] + step[2];
 
    // 각 계단까지의 최대 점수를 구하는 방법
    // 두 가지 경우 중 최댓값이 그 계단까지의 최대 점수가 된다.
    // (1) 현재 계단 밟기, 1 이전 계단 밟기, 2 이전 계단 밟지 않기
    // (2) 현재 계단 밟기, 1 이전 계단 밟지 않기, 2 이전 계단 밟기
    for (int i = 3; i <= n; i++)
    {
        dp[i] = max(step[i] + step[i - 1] + dp[i - 3], step[i] + dp[i - 2]);
    }
 
    printf("%d", dp[n]);
    return 0;
}