[Silver III] 계단 오르기 - 2579

문제 링크

성능 요약

메모리: 2024 KB, 시간: 0 ms

분류

다이나믹 프로그래밍

🥴 Hmm...

DP라서 규칙을 생각해봤다
처음엔 음 바로 전 계단과 바로 전전 계단 중 최댓값을 .. 비교하려 했는데 그러면
3번 연속 되는 걸 생각하기 어려워졌다. 음... 더 생각해보다가
아!

그럼 전전 계단이랑 전전전 계단을 생각해주면 되겠다 싶었다
그래서 코드를 슉슉 적었는데 바로 풀려서 기분 좋았다

🖥️ 소스코드

#define fastio ios_base::sync_with_stdio(false), cin.tie(0), cout.tie(0)
#include <iostream>
#include <vector>
#include <math.h>
#include <algorithm>
#include <queue>
#include <set>
#include <map>
#include <string.h>
using namespace std;

/* Method Initialization */
void input();
void solve();

/* Variable Initialization */
int n, mx;
int dp[304];
int a[304];


int main()
{
    fastio;
    //input();
    solve();
    return 0;
}

void input(){}
void solve()
{
    cin >> n;
    for(int i = 1; i <= n; i++) cin >> a[i];
    dp[0] = 0;
    dp[1] = a[1];
    dp[2] = a[1] + a[2];
    for(int i = 3; i <= n; i++){
        dp[i] = max(dp[i-2] + a[i], dp[i-3] + a[i-1] + a[i]);
    }
    cout << dp[n] << '\n';
}