BOJ : 2579 계단 오르기

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

첫 번째 계단부터 최대점수를 구하고... 

두 번째 계단의 최대점수 구하고...

....

마지막 계단의 최대 점수를 구하는 DP문제입니다.

첫번째 계단을 밟았을 때 최대값은 첫번째 계단을 밟았을 때 받게 되는 점수가 됩니다. sum[1] = step[1]

두번째 계단을 밟았을 때 최대값은 첫번째 계단을 밟고 두번째 계단을 밟았을 때 혹은 첫번째 계단을 밟지않고 2단 점프를 했을 때가 됩니다.

세번째 계단 또한 두번째 계단을 밟았을 때 혹은 첫번째 계단을 밟고 세번째계단으로 2단점프를 했을 때가 됩니다.

N번째 계단은 N-3번째 계단에서 N-1번째 계단까지 2단점프를 한 후, N번째 계단으로 점프를 했을 때 혹은 N-2번째 계단에서 2단점프를 했을 때가 됩니다.

이런식으로 N까지 반복하게 되면 N번째 계단을 밟았을 때 최대값을 구할 수가 있습니다.

#include <cstdio>
#include <algorithm>
using namespace std;

int main(){
    int N, step[301], sum[301]={0,};
    scanf("%d",&N);
    for(int i=1;i<=N;i++)
        scanf("%d",&step[i]);
    
    sum[1]= step[1];
    for(int i=2;i<=N;i++){
        sum[i] = max(step[i-1] + sum[i-3], sum[i-2])+step[i];
    }
    printf("%d\n",sum[N]);
}