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

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

 

 

계단 오르기 게임에서 얻을 수 있는 최대 점수를 구해야한다. 나는 이 문제를 DP로 풀어보았다. 우선 3개의 계단까지의 초기값을 설정해주고 점화식을 통해 n-1까지 dp배열을 추가해준다.

이때 규칙은 문제에서 주어진 것을 바탕으로 

 

• 계단은 한 번에 한 계단 또는 두 계단씩만 오를 수 있습니다.
• 연속된 세 개의 계단을 모두 밟을 수 없습니다.
• 마지막 계단은 반드시 밟아야 합니다.

이렇게 2개로 나눠볼 수 있다.

 

 

• dp[i-2] + v[i]: 두 계단 전에서 오는 경우
• dp[i-3] + v[i-1] + v[i]: 세 계단 전에서 현재 계단을 포함하여 두 개의 연속된 계단을 밟는 경우

정답코드

#include <iostream>
#include <vector>
#include <algorithm>
using namespace std;

int main() {
    int n;
    cin >> n;
    vector<int> v(n);
    vector<int> dp(n);

    for (int i = 0; i < n; i++) {
        cin >> v[i];
    }

    if (n == 1) {
        cout << v[0] << endl;
        return 0;
    }
    else if (n == 2) {
        cout << v[0] + v[1] << endl;
        return 0;
    }

    // 초기값 설정
    dp[0] = v[0];
    dp[1] = v[0] + v[1];
    dp[2] = max(v[0] + v[2], v[1] + v[2]);

    // 점화식을 이용하여 dp 배열 채우기
    for (int i = 3; i < n; i++) {
        dp[i] = max(dp[i - 2] + v[i], dp[i - 3] + v[i - 1] + v[i]);
    }

    cout << dp[n - 1] << endl;
    return 0;
}