[C언어/DP] 2579 : 계단 오르기

 

 

dp 배열 : i 번째 value값이 포함될때의 최댓값

(i번째 value값이 포함되지 않을 때의 값도 비교하는 바람에 틀렸었다. )

#include<stdio.h>
#define MAX 305

double max(double a,double b){
	return a>b?a:b;
}
int main(void){
	int n;
	double dp[MAX]={0},arr[MAX]={0};
	scanf("%d",&n);
	for(int i=1;i<=n;i++)
		scanf("%lf",&arr[i]);
	dp[1]=arr[1];
	dp[2]=arr[1]+arr[2];

	for(int i=3;i<=n;i++){
			dp[i]=max(dp[i-3]+arr[i-1]+arr[i],dp[i-2]+arr[i]);
	}

	printf("%.lf",dp[n]);
}