[BOJ] 계단 오르기(2579)

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

문제 : BOJ_2579번 계단 오르기

문제 설명

DP

각 계단마다 점수가 있고, 도착 지점까지 계단을 오르며 점수를 더해서 최댓값이 나와야 합니다.

이때 계단은 한 번에 한 계단이나 두 계단씩 오를 수 있고, 세 개의 계단을 연속해서 밟을 수는 없습니다.

그리고 마지막 도착 지점의 계단은 반드시 밟아야 합니다.

---

Solution

dp를 활용하여 해결하였습니다.

dp[현재 계단 인덱스][이전 계단과 연속해서 밟았는지의 유무] = 현재 계단까지의 최댓값으로 dp 식을 짜봤습니다.

현재 계단에서 이전 계단과 연속해서 밟지 않았다면, 현재 계단 인덱스-2의 계단에서의 최댓값을 갱신해 주어야 합니다.

이때 현재보다 2가 낮은 인덱스의 계단은 이전 계단과 연속해서 밟은 경우와 연속해서 밟지 않은 경우 모두 가능하므로 둘 중의 최댓값을 갱신해 주어야 합니다.

현재 계단에서 이전 계단과 연속해서 밟는다면, 이전 계단에서 연속해서 밟지 않은 경우에 현재 계단의 점수를 더해주면 최댓값이 됩니다.

---

Description

• 첫 번째 계단에 대해선, dp[1][0]=1번째 계단 점수, dp[1][1]=0으로 할당해 주고 시작했습니다.

---

#include <iostream>
#include <vector>
#include <algorithm>
using namespace std;
int n;
int dp[301][2];
vector<int> adj;
int main(){
    cin >> n;
    adj.resize(n+1);
    for(int i=1; i<=n; i++){
        cin >> adj[i];
    }
    dp[1][0]=adj[1];
    dp[1][1]=0;
    for(int i=2;i<=n;i++){
        dp[i][0]=max(dp[i-2][0],dp[i-2][1]);
        dp[i][0]+=adj[i];
        dp[i][1]=dp[i-1][0] + adj[i];
    }
    cout << max(dp[n][0],dp[n][1]) << '\n';
    return 0;
}