#include <stdio.h>

int max(int a,int b) {
    return a>b? a:b;
}

int num[301];
int bottom_up(int n) {
    int dp[301]={0};
    dp[0]=num[0];
    dp[1]=max(num[0],num[0]+num[1]);
    dp[2]=max(num[0]+num[2],num[1]+num[2]);

    for(int i=3; i<n; i++) {
        //계단 n자리에 올려면 
        //1. n-2번재 오기
        //2. n-1번째 오는데 n-2 안 밟기 -> 무조건 n-3 에서 오기
        dp[i]=max(num[i]+dp[i-2],num[i]+num[i-1]+dp[i-3]);
    }
    return dp[n-1];
}
int main() {
    int n;
    scanf("%d",&n);
    for (int i=0 ;i<n; i++) {
        scanf("%d",&num[i]);
    }
    printf("%d",bottom_up(n));
    return 0;
}

Embed on website

To embed this project on your website, copy the following code and paste it into your website's HTML: