[BOJ 2579] 계단 오르기

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

1. dp를 통해 차례로 구한다.

#include <iostream>

#include <algorithm>

using namespace std;

#define MAX_N 301

int i, N;

int a[MAX_N], dp[MAX_N], result;

void input()

{

cin >> N;

for (i = 1;i <= N;i++) cin >> a[i];

}

void cal()

{

dp[0] = 0; dp[1] = a[1]; dp[2] = a[1] + a[2];

for (i = 3;i <= N; i++)

dp[i] = max(a[i] + dp[i - 2], a[i] + a[i - 1] + dp[i - 3]);

result = dp[N];

}

int main()

{

input(); cal();

cout << result << endl;

}