[백준/DP/C++] 2579번 계단 오르기

https://www.acmicpc.net/problem/2579

2579번: 계단 오르기

한번에 한계단이나 두계단만 오를 수 있고 연속으로 세계단은 오를 수 없기 때문에
n-3계단에서 n-1을 건너 오는 경우(한계단)와 n-2에서 오는 경우(두계단)의 경우가 있을 수 있다

이 중 점수의 최대값을 구하면 된다

#include <bits/stdc++.h>

using namespace std;
int n;
int dp[301] = {0}, a[301] ={0};

int main(void) {
    cin >> n;

    for(int i=1; i<=n; i++){
        cin >> a[i];
        dp[i] = a[i];
    }

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

    cout << dp[n]<< endl;

    return 0;
}

반응형