[BOJ 2579] (DP)계단 오르기(C++)

계단 오르기 (Silver 3)

문제

전체 문제 보기

2579번: 계단 오르기

접근법

이 문제는 예전에 풀었던 BOJ 2156 포도주 시식 문제와 상당히 비슷하다.(포도주 시식 풀이) 포도주 시식 문제와의 차이점은 이 문제에서는 반드시 마지막 계단을 포함해야 한다는 점이다. 이번 문제에서도 3개의 계단을 연속으로 밟을 수 없다. 그래서 임의의 위치 $n$에서 점수의 최댓값을 $f(n)$, $n$의 점수를 $a(n)$이라고 했을 때 $f(n)$은 아래의 두 가지 경우 중 큰 값이 이다.

• $1$ 부터 $n-3$ 까지의 최댓값인 $f(n-3)$과 $a(n-2)$를 포기하고 $a(n-1)$과 $a(n)$을 취하는 경우
• $1$ 부터 $n-2$ 까지의 최댓값인 $f(n-2)$와 $a(n-1)$를 포기하고 $a(n)$을 취하는 경우

이를 점화식으로 정리하면 다음과 같다.

$$f(n) = \mbox{max} ( f(n-3) + a(n-1) + a(n), f(n-2) + a(n-1) )$$

구현

중복된 계산을 줄이기 위해서 한번 계산한 값은 cache 배열에 저장한다. 그리고 바텀업 방식으로 구현하였다.

#include <iostream>
#include <algorithm>
#include <array>
#define endl '\n'

using namespace std;
int main()
{
    //입출력 성능향상을 위한 설정
    ios_base::sync_with_stdio(false);
    cout.tie(NULL);
    cin.tie(NULL);
    const int MAX = 301;

    array<int, MAX> cache{};
    array<int, MAX> num{};
    int N; //N은 300이하의 자연수
    cin >> N;

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

    cache[1] = num[1];
    cache[2] = num[1] + num[2];

    for (int i = 3; i <= N; ++i)
    {
        cache[i] = max( cache[i - 3] + num[i - 1] + num[i], cache[i - 2] + num[i]);
    }

    cout << cache[N];
    return 0;
}

성능 평가

1부터 N까지의 최댓값을 하나씩 계산하기 때문에 시간 복잡도는 $O(n)$이다. 그리고 중복된 계산을 피하기 위해 모든 계산 결과를 cache 배열에 저장하고 N개 계단의 점수도 모두 저장하기 때문에 공간 복잡도 또한 $O(n)$이다.