백준 2579 계단 오르기, c++

 

 

 

작성한 코드는 다음과 같다.

max(dp[i-2], dp[i-3]+arr[i-1]) + arr[i]; 가 되는 이유:

ex. dp[4]를 구할 때 2,3,4인 경우가 이어서 건너게 되면 안되므로

i=2 에서 4로 가거나, i=1,3을 건너 4로 가는 경우로 고려해 주어야 함.

(i=3에서 4로 가는 경우로 하면 안됨, 2,3,4연속해서 가는 경우가 포함될 수 있음)

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

int main(){
    int n;
    cin >> n;
    
    int arr[n+1];
    for(int i=1; i<=n; i++)
        cin >> arr[i];
    
    int dp[n+1] = {0,};
    dp[1] = arr[1];
    dp[2] = arr[1]+arr[2];
    dp[3] = max(arr[1]+arr[3], arr[2]+arr[3]);
    for(int i=4; i<=n; i++){
        dp[i] = max(dp[i-2], dp[i-3]+arr[i-1]) + arr[i];
    }
    
    cout << dp[n];
    return 0;
}