#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;
}
To embed this project on your website, copy the following code and paste it into your website's HTML: