[BOJ_C++] 2579번 : 계단 오르기

code

#define _CRT_SECURE_NO_WARNINGS
#include <iostream>
#include <algorithm>
#include <cstring>
#include <stack>
#include <vector>
#include <cmath>
#include <string>

using namespace std;
int dp[301];

int main() {
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);
    cout.tie(NULL);

    memset(dp, 0, sizeof(dp));
    int n; cin >> n;
    int* list = new int[n];
    for (int i = 0; i < n; i++)
        cin >> list[i];

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

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

    cout << dp[n];

    return 0;
}

• 계단을 올라가는 방법을 다음과 같이 나누어 생각할 수 있다.

1. 한칸 + 한칸 + 두칸
2. 한칸 + 두칸

• 연속으로 세 번 계단을 모두 오를 수 없기 때문에 두 가지 경우의 수가 나오게 된다.
• 이때 마지막 계단은 꼭 밟아야 하므로 마지막 계단을 위주로 생각해보면 max(n-2 + n, n-3 + n-1 + n)을 구하는 문제가 된다.
• 점화식에 필요한 3개의 원소를 미리 계산한 뒤, max를 구하여 출력한 뒤 프로그램을 종료한다.

결과