[백준]2579-계단 오르기(Dynamic Programming)

계단을 오르는 방법은 2가지 방법이 있다. 한 계단씩 오르는 방법과 두 계단씩 오르는 방법.

그리고 제약조건으로 "연속된 세 개의 계단을 모두 밟아서는 안된다."가 있다.

 

조금 관점을 바꿔서, 올라올 계단의 입장에서 보자. 올라오는 방법은 한 계단 아래에서 올라오는 방법과 두 계단 아래에서 올라오는 방법이 있다.

 

그리고 s[i][1]을 "가장 마지막에 한 계단 아래에서 올라와서 i번째 계단으로 올라갔을 때의 최고 점수"라고 정의하자.

s[i][2]는 "가장 마지막에 두 계단 아래에서 올라와서 i번째 계단으로 올라갔을 때의 최고 점수"이다.

 

그럼 s[i][1]을 살펴보자.

한 계단 아래에서 올라왔다. 즉 i - 1번째 계단과 i번째 계단을 밟았다는 것이다. 따라서 이 방법을 골랐을 경우에는 i - 1번째 계단으로 올라갈 때 i - 3번째 계단에서 두 계단을 한 번에 올라오는 방법밖에 없다. i - 2번째 계단에서 올라왔다고 가정하면 i - 2, i - 1, i 이렇게 연속된 세 계단을 밟았다는 제약조건에 걸리니 모순이 발생한다.

따라서 위 내용을 식으로 정리하면

s[i][1] = s[i][0] + s[i - 1][2]; 이다.

s[i][0]은 i번째 계단의 점수이다.

 

그럼 s[i][2]는 어떨까?

일단 i - 2, i 이렇게 두 계단을 밟는다는 것은 확실하다. 두 계단을 한 번에 올라왔으니 i - 1번째 계단은 밟지 않는다.

따라서 s[i][2]는 s[i - 2][1]과 s[i - 2][2]중 더 큰 값을 더하면 된다.

식으로 정리하면

s[i][2] = s[i][0] + max(s[i - 2][1], s[i - 2][2]); 이다.

//#define _CRT_SECURE_NO_WARNINGS
#include <cstdio>
using namespace std;
 
int stair(int num, int** sta);
 
int main() {
    int N;
    scanf("%d", &N);
    int** sta = new int* [N + 1];
    sta[0] = new int[3];
    sta[0][0] = sta[0][1] = sta[0][2] = 0;
    for (int i = 1; i <= N; i++) {
        sta[i] = new int[3];
        int num;
        scanf("%d", &num);
        sta[i][0] = sta[i][1] = sta[i][2] = num;
    }
    printf("%d\n", stair(N, sta));
    for (int i = 0; i <= N; i++)
        delete[] sta[i];
    delete[] sta;
}
 
int stair(int num, int** sta) {
    for (int i = 2; i <= num; i++) {
        sta[i][1] += sta[i - 1][2];
        sta[i][2] += sta[i - 2][1] > sta[i - 2][2] ? sta[i - 2][1] : sta[i - 2][2];
    }
    return sta[num][1] > sta[num][2] ? sta[num][1] : sta[num][2];
}

간단한 코드이니 참고하면 좋을 듯하다.