백준 2579: 계단 오르기

힌트 : 다이나믹 프로그래밍을 이용해 점화식을 세워보자 첫번 째로 계단을 올라온 경우 두번 째로 계단을 올라온 경우

첫번 째로 계단을 올라온 경우는 두 칸아래 계단을 첫 번째로 올라왔는지 두 번째로 올라왔는지 상관 없이 올라올 수 있고

두번 째로 올라온 계단은 직전 계단의 첫번째로 올라온 경우에만 올라올 수 있다. 점화식을 세워보자!

#include <iostream>
#include <algorithm>
using namespace std;
int point[350];
long long d[350][2];
 
int main()
{
    int input = 0;
    cin >> input;
    for (int i = 1; i <= input; ++i)
        cin >> point[i];
    d[1][0] = d[1][1] = point[1];
    for (int i = 2; i <= input; ++i)
    {
        d[i][0] = max(d[i - 2][1], d[i - 2][0]) + point[i];
        d[i][1] = d[i - 1][0] + point[i];
    }
    long long ans = 0;
    ans = d[input][0] > d[input][1] ? d[input][0] : d[input][1];
    cout << ans << endl;
}