BOJ 2579 계단 오르기

boj 2579 계단 오르기

문제의 조건에 따라 마지막 계단은 무조건 밟아야한다. 계단은 연속으로 두번까지 밟을 수 있다. 마지막 계단을 밟는데, 그 마지막 계단이 연속으로 밟은 첫번째 계단이냐 두번째 계단이냐로 경우의 수를 나눌 수 있다. 이를 바탕으로 테이블을 정의해보자.

D[i][1] = 마지막 계단이 i번째 계단이고 1개의 계단을 연속으로 밟은 경우, 계단 점수 합의 최댓값
D[i][2] = 마지막 계단이 i번재 계단이고 2개의 계단을 연속으로 밟은 경우, 계단 점수 합의 최댓값

D[i][1]의 경우는 i-1번째 계단을 밟지 않으므로, 마지막 계단이 i-2번째 계단일 경우의 계단 점수의 최댓값에서 i번째 계단 점수를 더하면 된다. D[i][2]의 경우는 i-1번째 계단을 무조건 밟고, i-2번째 계단을 무조건 밟지 않으므로 D[i-1][1]에다가 i번째 계단 점수를 더하면 된다. 계단 점수를 담는 배열을 score[i]라고 할때, 이를 바탕으로 점화식을 만들어보자.

D[i][1] = max(D[i-2][1], D[i-2][2]) + score[i]
D[i][2] = D[i-1][1] + score[i]

이를 바탕으로 코드를 구현해보자.

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

int num;
int score[305];
int D[305][3];

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

    cin >> num;
    for (int i = 1; i <= num; i++) cin >> score[i];

    if (num == 1)
    {
        cout << score[1];
        return 0;
    }

    D[1][1] = score[1];
    D[1][2] = 0;
    D[2][1] = score[2];
    D[2][2] = score[1] + score[2];

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

    cout << max(D[num][1], D[num][2]);

    return 0;
}