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

 📚 문제

[BOJ C++] 백준 2579번: 계단 오르기
https://www.acmicpc.net/problem/2579

 

---

 📝 입력 및 출력

 

---

 🔎 문제 풀이

v 에는 각 계단에 쓰여있는 점수 자체를, dp에는 각 계단까지의 누적 최대 점수를 저장한다. 첫 번째 계단은 계단에 쓰인 점수 자체가 최댓값이고, 두 번째 계단은 첫 번째 계단의 점수 + 두 번째 계단의 점수가 최댓값이 된다. (각 계단의 점수는 자연수이므로 숫자 1개보단 2개를 더한 값이 당연히 더 크기 때문.)

 

세 번째 계단부터는 dp를 활용하여 문제를 해결할 수 있다.

1. 1칸 + 2칸
2. 2칸 + 1칸
3. 1칸 + 1칸 + 1칸 ( X )

위와 같이 세 가지 방법으로 나누어 볼 수 있지만, 이 문제에서 3번 방법은 허용하지 않는다.

 

네 번째 계단에서는

1. 1칸 + 1칸 + 1칸 + 1칸 ( X )
2. 1칸 + 1칸 + 2칸
3. 1칸 + 2칸 + 1칸
4. 2칸 + 1칸 + 1칸
5. 2칸 + 2칸

이 가능한데, 1번 방법은 4번이나 연속하기 때문에 불가능하다. 1번 경우를 제외하고 다른 경우들을 다시 잘 살펴보면

2. (1칸 + 1칸) + 2칸
3. (1칸 + 2칸) + 1칸
4. (2칸 + 1칸) + 1칸
5. (2칸) + 2칸

와 같이 묶을 수 있고, 2번 계단에서 두 칸 올라가는 경우(2, 5)와 3번 계단에서 한 칸 올라가는 경우(3, 4)로 해석할 수 있다.

 

즉, 계단을 오를 때 최대 점수를 얻는 방법은

1️⃣ 직전 계단을 밟고 올라오는 경우
2️⃣ 두 계단 전에서 건너뛰고 올라오는 경우

로 나눌 수 있고, 이를 바탕으로 점화식을 도출할 수 있다.

 

1️⃣ 직전 계단을 밟고 올라오는 경우

dp[i] = dp[i - 3] + v[i - 1] + v[i];

2️⃣ 두 계단 전에서 건너뛰고 올라오는 경우

dp[i] = dp[i - 2] + v[i];

 

따라서 i번 계단의 누적 점수가 최대가 되기 위해서는 두 값 중 더 큰 값을 선택하여 dp[i]에 저장하면 된다.

---

 ⌨️ C++ 코드

#include <bits/stdc++.h>
using namespace std;

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

    int n;
    cin >> n;
    vector<int> v(n + 1), dp(n+1);
    for (int i = 1; i <= n; i++) cin >> v[i];
    dp[1] = v[1];
    dp[2] = v[1] + v[2];

    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];
}