계단 오르기

문제: 계단 오르기 (백준 2579번)

문제

입력 및 출력

구조 분석

해당 문제는 전형적인 dynamic programming 문제이다. Dynamic programming을 이용하고자 한 근거는 다음과 같다.

1. n번째 계단에서의 점수를 dp(n)이라고 하자.
2. dp(n) = max(dp(n-1), dp(n-2)) 와 같은 구조를 갖는다.
   • 피보나치: fib(n) = fib(n-1) + fib(n-2)
   • 계단문제: dp(n) = max(dp(n-1) , dp(n-2))
   • 피보나치에서 +연산이 max연산으로 변경된 것 뿐이다.

조건 분석

1. 계단은 한번에 하나 또는 두개씩 오른다.
   • dp(n) = max(dp(n-1), dp(n-2)) 구조를 갖는다.
   • n번째 계단 전에 n-1번째 계단 또는 n-2번째 계단을 밟는다.
2. 연속된 세 계단을 모두 밟을 수 없다.
   • dp(n) = max(dp(n-2) + point(n), dp(n-3) + point(n-1) + point(n))
3. 마지막 계단을 밟는다.
   • dp(n)의 값을 반환한다.

코드

#include <stdio.h>
#include <stdlib.h>
#include <iostream>
#define MAX(a,b) (((a)>(b))?a:b)
using namespace std;

int point[301] = {0,};
int dp[301] = {0,};

int main() {
    cin.tie(NULL);
    cout.tie(NULL);
    int n;
    cin >> n;
    for (int i=1; i<=n; i++) {
        cin >> point[i];
    }
    dp[1] = point[1];
    dp[2] = point[1] + point[2];
    dp[3] = MAX(point[1]+point[3],point[2]+point[3]);

    for (int i=4; i<=n; i++) {
        dp[i] = MAX(dp[i-2]+point[i],dp[i-3]+point[i-1]+point[i]);
    }
    cout << dp[n] << "\n";
    return 0;
}

정리

Bottom up 방식의 dynamic programming을 이용하여 해결했으며, O(N)의 시간복잡도, O(N)의 공간복잡도를 갖는다. 문제의 조건때문에 당황할 수 있지만 구조를 파악하면 잘 해결할 수 있다.