백준 2579번 [계단 오르기] (C++) -yes6686- 티스토리

백준 문제 풀이: 2579 [계단 오르기]

---

문제 링크: https://www.acmicpc.net/problem/2579

문제 설명:

계단 오르기 게임에서 점수를 최대로 하기 위한 문제입니다. 계단은 한 번에 1칸 또는 2칸씩 오를 수 있으며, 연속된 세 개의 계단을 밟을 수 없습니다. 각 계단에는 점수가 주어지고, 마지막 계단은 반드시 밟아야 합니다.

---

문제 해결 코드

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

int arr[301]; // 각 계단의 점수
int dp[301];  // 해당 계단까지의 최대 점수

int main() {
    int n; // 계단의 개수
    cin >> n;

    // 계단 점수 입력
    for (int i = 1; i <= n; i++) {
        cin >> arr[i];
    }

    // 초기값 설정
    dp[0] = 0; // 시작점은 점수 없음
    dp[1] = arr[1]; // 첫 번째 계단 점수
    dp[2] = arr[1] + arr[2]; // 두 번째 계단 점수 (연속해서 밟음)

    // 동적 프로그래밍으로 최대 점수 계산
    for (int i = 3; i <= n; i++) {
        dp[i] = max(arr[i] + arr[i - 1] + dp[i - 3], // i-1, i 계단을 밟는 경우
                    arr[i] + dp[i - 2]); // i 계단만 밟는 경우
    }

    // 결과 출력
    cout << dp[n] << '\n';

    return 0;
}

---

코드 설명

• 핵심 알고리즘: 동적 프로그래밍을 사용하여, 계단을 밟는 두 가지 경우를 고려하며 최댓값을 계산합니다.
• 구현 세부사항:
  • dp[i]: i번째 계단까지 도달했을 때의 최대 점수
  • 점화식:
    • dp[i] = max(arr[i] + arr[i-1] + dp[i-3], arr[i] + dp[i-2])
    두 경우를 비교하여 최댓값을 선택:
    • 현재 계단(i)과 이전 계단(i-1)을 밟고 i-3 계단에서 오는 경우
    • 현재 계단(i)만 밟고 i-2 계단에서 오는 경우
• 시간 복잡도 분석: O(n)
  • 각 계단에 대해 상수 시간 연산을 수행합니다.

---

결과

계단을 밟는 규칙을 준수하면서 얻을 수 있는 최대 점수를 정확히 계산합니다. 동적 프로그래밍을 활용하여 효율적으로 해결했습니다.

다른 접근 방식이나 개선 사항이 있다면 댓글로 공유 부탁드립니다!