백준 2579 (계단 오르기)

기본적인 DP 문제였다.

처음에는 1차원 dp 로 생각하려 했다. 그런데 i 번째로 올 수 있는 경우의 수가 많아서 1차원 dp 는 안된다는 걸 알았다.

그래서 0, 1, 2 로 dp 를 나눠서 생각하기로 했다.

x == 0 : 0 은 x 번째 계단을 선택하지 않는 것

x == 1 : 1 은 x 번째 계단을 선택하고 x-1 은 선택하지 않는 것

x == 2 : 2 는 x 번째, x-1 번째 계단을 선택하고 x-2 번째 계단은 선택하지 않는 것

 

<문제링크>

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

 

<소스코드>

#include <iostream>
#include <algorithm>
#include <string>
#include <vector>
#include <queue>
#include <cmath>
#include <typeinfo>

using namespace std;

int dp[3][301];
int stair[301];
int N, inp;

int main(){
    
    cin.tie(NULL);
    ios::sync_with_stdio(false);
    
    cin >> N;
    
    for (int i = 0; i < N; i++) {
        cin >> inp;
        stair[i] = inp;
    }
    
    dp[0][0] = 0; dp[1][0] = stair[0]; dp[2][0] = 0;
    
    dp[0][1] = stair[0];
    dp[1][1] = stair[1];
    dp[2][1] = stair[0] + stair[1];
    
    dp[0][2] = stair[0] + stair[1];
    dp[1][2] = stair[0] + stair[2];
    dp[2][2] = stair[1] + stair[2];
    
    for (int i = 3; i < N; i++) {
        dp[0][i] = max({dp[1][i-1], dp[2][i-1]});
        dp[1][i] = max({dp[1][i-2] + stair[i], dp[2][i-2] + stair[i]});
        dp[2][i] = max({dp[1][i-3] + stair[i] + stair[i-1], dp[2][i-3] + stair[i] + stair[i-1]});
    }
    
    cout << max(dp[1][N-1], dp[2][N-1]) << '\n';
    
    return 0;
}