[백준/BOJ] 2579번 계단 오르기 (C++)

www.acmicpc.net/problem/2579

2579번: 계단 오르기

DP 유형의 문제입니다.

마지막 계단을 오를 때 다음과 같이 두가지로 경우로 나눠서 생각합니다. 
연속 O 도착
연속 X 도착

연속 O 도착인 경우, 그 전 계단을 오른 건 무조건 연속 X 입니다. 왜냐하면 연속이 되어버리면 3계단 연속이 되어버려 문제의 조건을 만족할 수 없게 됩니다. 그래서 연속 O 도착의 점화식은 다음과 같이 나타낼 수 있습니다.

 

dp[n][1] = dp[i - 1][0] + v[i]

 

그러나 연속 X 도착인 경우, 그 전 계단을 오른게 연속 O 혹은 연속 X가 될 수 있습니다. 따라서 그 두가지 케이스 중에서 최대값인것을 구하여 마지막 계단의 값을 더해줘야합니다.

 

dp[n][0] = max(dp[i - 2][0], dp[i - 2][1]) + v[i]

 

마지막으로 dp[n][0]과 dp[n][1] 중 더 큰 값을 출력하면 됩니다.

 

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

int dp[301][2]; // 0 : 연속 X, 1 : 연속 O

int main(void) {
    ios_base::sync_with_stdio(false);
    cin.tie(0);
    
    int n;
    cin>>n;
    vector<int> v(n + 1);
    for(int i = 1; i <= n; i++) {
        cin>>v[i];
    }
    
    dp[1][0] = v[1];
    dp[2][0] = v[2];
    dp[2][1] = v[1] + v[2];
    for(int i = 3; i <= n; i++) {
        dp[i][0] = max(dp[i - 2][0], dp[i - 2][1]) + v[i]; // 연속 X 도착한 경우
        dp[i][1] = dp[i - 1][0] + v[i]; // 연속 O 도착한 경우
    }
    
    cout<<max(dp[n][0], dp[n][1]);
}