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

문제 링크

문제 풀이

DP를 이용하여 문제를 해결하였다. N번째 계단을 한 번 밟았을 때의 최대 점수를 dp1, 두 번 밟았을 때를 dp2에 저장하고 해당 칸을 밟았을 때의 최대 점수를 dp에 저장하였다.

코드

#include <iostream>

using namespace std;

int dp1[400]; // 계단 한 번 밟기
int dp2[400]; // 계단 두 번 밟기
int dp[400];

int scores[400];
int N;

int main(void)
{
    ios::sync_with_stdio(false);
    cin.tie(nullptr);

    cin >> N;

    for (int i = 1; i <= N; i++)
        cin >> scores[i];

    dp1[1] = scores[1];
    dp2[1] = 0;
    dp[1] = scores[1];

    dp1[2] = scores[2];
    dp2[2] = scores[1] + scores[2];
    dp[2] = scores[1] + scores[2];

    for (int i = 3; i <= N; i++)
    {
        dp1[i] = dp[i - 2] + scores[i];
        dp2[i] = dp1[i - 1] + scores[i];
        dp[i] = max(dp1[i], dp2[i]);
    }

    cout << dp[N] << '\n';

    return 0;
}