2579번: 계단 오르기

2579번: 계단 오르기

사용 언어: C++

 

문제 요약

• 계단은 아래에서 위로 올라가며, 각 계단에는 점수가 적혀 있음.
• 계단은 1칸 또는 2칸씩 오를 수 있음.
• 단, 연속된 3개의 계단을 모두 밟는 것은 금지됨.
• 마지막 계단은 반드시 밟아야 함.
• 시작점은 계단에 포함되지 않음.
• 주어진 계단 점수 배열에서, 규칙을 지키며 밟을 수 있는 최대 점수의 합을 구하는 문제.

 

풀이

처음엔 재귀로 풀어보려 했지만 연속된 3계단을 밟을 수 없다는 제약 때문에 코드가 복잡해졌고,
"더 좋은 방법이 있겠지" 싶어서 Bottom-Up DP 방식으로 전환했다.

 

• dp[i] = i번째 계단까지 도달했을 때의 최대 점수
• 두 가지 경우만 고려한다:
  1. dp[i-2] + stairs[i] → 한 칸 건너뛰고 오기
  2. dp[i-3] + stairs[i-1] + stairs[i] → 두 칸 건너뛰고 연속 두 칸 밟기
     → 세 칸 연속 방지용 구조

 

dp[i] = max(dp[i-2], dp[i-3] + stairs[i-1]) + stairs[i] // 칸 i의 최대 점수

그래서 코드를 작성한 결과

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

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

    int n;
    cin >> n;

    vector<int> stairs(n + 1);
    vector<int> dp(n + 1);

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

    dp[1] = stairs[1];
    if(n >= 2)
    {
        dp[2] = stairs[1] + stairs[2];
    }
    if(n >= 3)
    {
        dp[3] = max(stairs[1] + stairs[3], stairs[2] + stairs[3]);
    }

    for(int i=4; i<=n; i++)
    {
        dp[i] = max(dp[i-2], dp[i-3] + stairs[i-1]) + stairs[i];
    }

    cout << dp[n] << '\n';

    return 0;
}