[BOJ] 2579 - 계단 오르기 (C++)

문제

계단 오르기

코드

#include <iostream>

using namespace std;

int dp[301], arr[301];
int N;

int main(void){
    cin.tie(0);
    ios_base::sync_with_stdio(false);

    cin >> N;
    for (int i = 0; i < N; i++) cin >> arr[i];

    dp[0] = arr[0];
    dp[1] = max(arr[1], arr[0]+arr[1]);
    dp[2] = max(arr[0]+arr[2], arr[1]+arr[2]);

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

접근

계단은 연속해서 세 칸은 오를 수 없고 한 칸이나 두 칸을 오를 수 있다. 따라서 현재 칸에 도달하는 경우는 2칸 이전에서 오거나 한칸 이전에서 온 경우인데 이때 한칸, 한칸, 한칸은 불가능하므로 필히 두칸, 한칸, 한칸으로 이동해야 한다. 이를 통해 다음과 같은 점화식을 만들어 낼 수 있다.

dp[i] = max(arr[i]+dp[i-2], arr[i]+dp[i-1]+dp[i-3])

이 점화식을 i=3부터 실행할 때 필요한 base condition인 0,1,2의 값은 직접 채워주었다.