백준 2579: 계단 오르기

Silver III 난이도 문제를 C++로 풀이한 내용입니다. 계단을 오를 때 얻는 점수의 최댓값을 찾는 동적 계획법(Dynamic Programming) 문제입니다.

문제 소개

• 문제 번호: 2579
• 문제명: 계단 오르기
• 난이도 (티어): Silver III
• 사용 언어: C++
• 실행 시간: 0 ms
• 메모리: 2020 KB
• 문제 요약: n개의 계단이 있고, 각 계단을 밟을 때마다 점수를 얻습니다. 연속으로 세 계단을 밟을 수 없으며, 마지막 계단을 반드시 밟아야 합니다. 이때 얻을 수 있는 총 점수의 최댓값을 구하는 문제입니다.

접근 방법

이 문제는 마지막 계단을 밟기 직전까지의 상태를 고려하여 최적의 경로를 찾아야 합니다. 각 계단에 도달했을 때 얻을 수 있는 최대 점수를 저장하고, 이전 상태들을 바탕으로 현재 상태의 최대 점수를 계산하는 방식으로 접근했습니다. 이는 전형적인 동적 계획법(Dynamic Programming) 문제입니다.

사용 알고리즘/자료구조

• 동적 계획법 (Dynamic Programming): 문제를 작은 부분 문제로 나누고, 부분 문제의 해결 결과를 저장하여 전체 문제의 해결에 활용합니다.
• 1차원 배열 (vector<int> dp): dp[i]는 i번째 계단에 도달했을 때 얻을 수 있는 최대 점수를 저장하는 데 사용합니다.
• 1차원 배열 (vector<int> score): score[i]는 i번째 계단의 점수를 저장하는 데 사용합니다.

선택 이유

각 계단에서의 최적의 선택은 이전 계단들에서의 최적의 선택에 의존합니다. 예를 들어, i번째 계단에 도달하는 방법은 i-1에서 올라오거나 i-2에서 올라오는 두 가지 경우가 있지만, '연속 세 계단 금지'라는 제약 조건 때문에 i-1에서 올라오는 경우는 i-2를 밟았는지 여부에 따라 경우의 수가 달라집니다. 이러한 상태 의존성을 효율적으로 관리하기 위해 동적 계획법이 적합하다고 판단했습니다.

풀이 과정

1. 입력 받기: 계단의 개수 n과 각 계단의 점수 score[1]부터 score[n]까지 입력받습니다.
2. DP 배열 초기화: dp 배열을 n+1 크기로 선언합니다. dp[i]는 i번째 계단에 도달했을 때 얻을 수 있는 최대 점수를 저장합니다.
3. 기저 사례 처리:
   • n=1: dp[1] = score[1] (첫 번째 계단만 밟음)
   • n=2: dp[2] = score[1] + score[2] (두 계단을 연속으로 밟음)
   • n=3: dp[3] = max(score[1] + score[3], score[2] + score[3]) (세 번째 계단에 도달하는 방법은 1->3 또는 2->3입니다. 1->2->3은 연속 세 계단이므로 불가능합니다.)
4. 점화식 정의: i번째 계단에 도달하는 방법은 두 가지로 나눌 수 있습니다.
   • Case 1: i-2 계단을 밟고 i 계단으로 바로 오는 경우: 이 경우 i-1 계단을 건너뛰므로 연속 계단 제약에 문제가 없습니다. 이전에 i-2 계단까지 얻은 최대 점수인 dp[i-2]에 현재 i 계단의 점수 score[i]를 더합니다. (dp[i-2] + score[i])
   • Case 2: i-3 계단을 밟고 i-1 계단을 거쳐 i 계단으로 오는 경우: i-1 계단을 밟았다면, i-2 계단을 밟을 수 없습니다. 따라서 i-1 계단에 도달하기 위해서는 반드시 i-3 계단을 밟고 i-2를 건너뛴 상태여야 합니다. 이전에 i-3 계단까지 얻은 최대 점수인 dp[i-3]에 i-1과 i 계단의 점수를 더합니다. (dp[i-3] + score[i-1] + score[i])
   • dp[i]는 이 두 경우 중 더 큰 점수를 선택합니다: dp[i] = max(dp[i-2] + score[i], dp[i-3] + score[i-1] + score[i])
5. 반복 계산: i를 4부터 n까지 증가시키며 점화식을 사용하여 dp[i]를 계산합니다.
6. 결과 출력: 마지막 계단 n을 반드시 밟아야 하므로, dp[n]이 최종 결과가 됩니다.

주의할 점

• 계단 인덱스가 0부터 시작하는 것이 아니라 1부터 시작하므로 배열 접근 시 인덱스 관리에 유의해야 합니다. (문제에서는 1부터 시작하지만, 코드에서는 편의상 0번째 계단을 땅으로 간주하여 score와 dp 배열을 1부터 사용했습니다.)
• n이 1, 2, 3일 때의 기저 사례 처리가 중요합니다. 점화식은 i >= 4일 때 적용되므로, n이 작은 경우에 대한 처리를 별도로 해주어야 합니다.

코드 설명

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

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

    int n;
    cin >> n;

    // score[i] : i번째 계단의 점수, 0번째 = 땅
    // dp[i]    : i번째 계단에 도달했을 때 얻을 수 있는 최대 점수
    vector<int> score(n+1), dp(n+1);

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

    // ===== 초기값 =====
    // 계단이 1개일 때: 그냥 밟는 수밖에 없음
    // 0 -> 1
    dp[1] = score[1];

    // 계단이 2개일 때:
    // 0 -> 1 -> 2 로 가는 게 최대 (계단 연속 2칸까지는 허용)
    if(n >= 2)
        dp[2] = score[1] + score[2];

    // 계단이 3개일 때:
    // 0 -> 1 -> 3
    // 0 -> 2 -> 3
    // (1 -> 2 -> 3 은 3연속이라 불가능)
    if(n >= 3) {
        dp[3] = max(
            score[1] + score[3],  // 0 -> 1 -> 3
            score[2] + score[3]   // 0 -> 2 -> 3
        );
    }

    // ===== 점화식 =====
    for(int i = 4; i <= n; i++) {

        // i에 도착하는 방법은 딱 두 가지뿐

        // Case 1: i-2 -> i
        // 한 칸 건너뛰므로 연속성 리셋 (항상 안전)
        int case1 = dp[i-2] + score[i];

        // Case 2: i-3 -> i-1 -> i
        // i-1을 밟고 오고 싶으면,
        // i-2를 밟으면 안 되므로 반드시 i-3에서 와야 함
        // (이게 연속 2칸의 유일한 합법 루트)
        int case2 = dp[i-3] + score[i-1] + score[i];

        // 두 경우 중 더 큰 점수 선택
        dp[i] = max(case1, case2);
    }

    // 마지막 계단은 반드시 밟아야 하므로 dp[n]이 정답
    cout << dp[n];
}

• ios::sync_with_stdio(false); cin.tie(NULL);: C++ 표준 스트림의 속도를 최적화하여 입출력을 빠르게 합니다.
• vector<int> score(n+1), dp(n+1);: 계단 점수와 DP 테이블을 저장할 벡터를 선언합니다. 0번 인덱스를 사용하지 않고 1부터 n까지 사용하기 위해 크기를 n+1로 설정했습니다.
• dp[1] = score[1];: 첫 번째 계단의 경우, 해당 계단 점수만큼만 얻을 수 있습니다.
• dp[2] = score[1] + score[2];: 두 번째 계단의 경우, 첫 번째와 두 번째 계단을 모두 밟는 것이 최적입니다.
• dp[3] = max(score[1] + score[3], score[2] + score[3]);: 세 번째 계단의 경우, 1->3 또는 2->3 경로만 가능하며, 더 높은 점수를 선택합니다. 1->2->3은 연속 세 계단이라 불가능합니다.
• for(int i = 4; i <= n; i++): 4번째 계단부터 n번째 계단까지 점화식을 적용하여 DP 테이블을 채웁니다.
• int case1 = dp[i-2] + score[i];: i-2 계단에서 i 계단으로 오는 경우의 최대 점수입니다.
• int case2 = dp[i-3] + score[i-1] + score[i];: i-3 계단에서 i-1 계단을 거쳐 i 계단으로 오는 경우의 최대 점수입니다.
• dp[i] = max(case1, case2);: i 계단에 도달하는 두 가지 경우 중 더 큰 값을 dp[i]에 저장합니다.
• cout << dp[n];: 최종적으로 n번째 계단에 도달했을 때 얻을 수 있는 최대 점수를 출력합니다.

복잡도 분석

• 시간 복잡도: O(N)
  • 입력을 받는 데 O(N) 시간이 소요됩니다.
  • DP 테이블을 채우는 과정에서 n번의 반복문이 수행되며, 각 반복 안에서는 상수 시간(O(1))의 연산이 이루어집니다. 따라서 DP 계산에 O(N) 시간이 소요됩니다.
  • 총 시간 복잡도는 O(N)입니다.
• 공간 복잡도: O(N)
  • 계단 점수를 저장하는 score 벡터와 DP 테이블을 저장하는 dp 벡터 모두 O(N) 크기를 가집니다.
  • 따라서 총 공간 복잡도는 O(N)입니다.

배운 점

이 문제는 동적 계획법의 기본적인 아이디어를 잘 보여줍니다.

• 최적 부분 구조: 문제의 최적 해는 부분 문제의 최적 해로부터 구성될 수 있습니다. i번째 계단에서의 최대 점수는 i-2 또는 i-3 계단에서의 최대 점수에 기반합니다.
• 중복 부분 문제: i번째 계단에서의 최적 점수를 계산하기 위해 i-2 또는 i-3 계단에서의 최적 점수가 반복적으로 사용될 수 있습니다. DP 테이블에 저장함으로써 불필요한 재계산을 피할 수 있습니다.
• 제약 조건의 중요성: "연속 세 계단을 밟을 수 없다"는 제약 조건이 DP 상태 전이(state transition)를 정의하는 데 핵심적인 역할을 했습니다. 이 제약 조건 때문에 i에 도달하는 방법이 i-1에서 오는 경우와 i-2에서 오는 경우 외에 i-3에서 i-1을 거쳐 오는 특별한 경우로 구분되었습니다.

이 문제를 통해 동적 계획법을 적용할 때,

1. 문제를 어떻게 작은 부분 문제로 나눌 것인가?
2. 부분 문제의 결과를 어떻게 저장하고 활용할 것인가?
3. 이전 상태로부터 현재 상태를 계산하는 정확한 점화식은 무엇인가?
4. 초기 조건(기저 사례)은 무엇인가?

등을 명확히 정의하는 것이 중요하다는 것을 다시 한번 확인할 수 있었습니다. 이러한 접근 방식은 계단 오르기 문제뿐만 아니라 다양한 최적화 문제에 적용될 수 있습니다.