[BOJ/C++] 2579번 : 계단 오르기

풀이

 

i번째 계단을 올랐을 때까지의 총 점수의 최댓값은

1. DATA[i] + DP[i-2]

2. DATA[i] + DATA[i-1] + DP[i-3] 

중에서 MAX값을 구한 것이다.

 

예외)

마지막 계단인 n번째 계단은 꼭 올라야 하므로 n-1와 n-2 모두를 오를 수는 없다.

따라서, n-1번째 계단은 예외적으로 DP[n-1]=DATA[n-1]+DP[n-3] 이다.

 

 

코드

#include <stdio.h>
#include <iostream>
#include <cstdio>
using namespace std;
#define MAX 300
 
 
int main(){
    int dp[MAX+1], data[MAX+1];
    int maxNum;
    int n;
    
    scanf("%d", &n);
    
    for(int i=1;i<=n;i++){
        scanf("%d", &data[i]);
    }
    
    dp[1]=data[1];
    dp[2]=data[1]+data[2];
    dp[3]=max(data[3]+data[1],data[3]+data[2]);
    
    
    for(int i=4;i<=n;i++){
        
        dp[i]=max(data[i]+dp[i-2], data[i]+data[i-1]+dp[i-3]);
        if(i==n-1) {dp[i]=data[i]+dp[i-2];}
    }
    
 
    
    
    printf("%d", dp[n]);
    
}