[백준] 2579번 : 계단 오르기

문제

 

---

풀이

 

동적계획법의 대표적인 문제 중 하나이다. 생각해보니 동적계획법은 대표하는 문제가 많은 것 같다...아무튼

이전까지의 문제들은 초기값을 받은 배열을 그대로 갱신하면서 값을 구했다. 하지만 이 문제는 그러면 안된다.

 

i번째 계단을 밟는다고 생각하자. i번째 계단을 밟기 위해선 어떤 경로로 계단을 밟아야 했을까?

i-3번째 계단을 밟고 i-1번째 계단을 밟은 뒤 i번째 계단을 밟거나(3번연속 계단을 밟을 수 없기 때문)

i-2번째 계단을 밟고 i-1번째 계단을 건너뛰고 i번째 계단을 밟을 수 있을 것이다.

 

배열을 1개만 사용하면 안되는 이유가 이것이다.

i번째의 계산을 할 때 i-1번째만 연속적으로 참조하던 지난 문제들과 달리 이건 불연속적으로? 지난 값들을 참고하기 때문에 초기 입력을 저장할 배열과 최댓값만 저장할 배열을 따로 만들어야 한다.

 

아무튼 대충 바닥을 0번째 계단으로 치고(1번째 계단부터 시작한다는 말) 점화식으로 정리하면

stair_max[i] = stair[i] + max(stair[i - 1] + stair_max[i - 3], stair_max[i - 2]); //i>2

이렇게 된다.

 

i<=2일때는 뭐 다 밟아도 괜찮으니 모든 계단을 밟은 값이 max가 될 것이다.

---

소스코드

 

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

int stair[301] = { 0, };
int stair_max[301] = { 0, }; //배열 하나에 갱신하지 말고 최대값만 저장할 배열을 생각했어야 함

int jump_stair(int num) {
    for (int i = 0; i <= num; i++) {
        if (i < 3) {
            for (int j = 0; j <= i; j++)
                stair_max[i] += stair[j];
        }
        else { //점화식을 먼저 짜보자. 배열 하나로 할 생각 X
            stair_max[i] = stair[i] + max(stair[i - 1] + stair_max[i - 3], stair_max[i - 2]);
        }
    }
    return stair_max[num];
}

int main() {
    int N;

    cin >> N;
    for (int i = 1; i <= N; i++)
        cin >> stair[i];
    cout << jump_stair(N);
}