[Baekjoon] 2579번 계단 오르기.cpp

[백준] 2579번 계단 오르기 문제 링크

쉬운 DP 문제이지만 간과하지 말아야 할 부분이 있다.

마지막 계단은 반드시 밟아야 하지만, 첫 계단은 밟지 않아도 된다는 것이다. 이를 유의하여 코드를 작성해야 한다.

· 메인 아이디어

연속으로 계단을 밟은 수가 3 이상이 되어선 안 되고, 0일 수는 없다. 아무런 계단도 밟지 않는 경우는 없기 때문이다. 따라서 특정 순서의 계단을 밟을 때 연속으로 계단을 밟은 수가 1인지 2인지에 따라 처리를 해주었다.

연속으로 두 개의 계단을 밟아왔다면 다음 계단은 밟을 수 없다. 연속으로 밟은 계단 수가 1일 때만 다음 계단을 밟을 수 있다.

하지만 한 칸을 건너뛰고 밟는 것은 연속으로 밟은 계단 수가 중요하지 않다. 이 경우는 연속으로 몇 개의 계단을 밟았던 누적된 점수가 높은 쪽의 점수를 가져가는 것이 유리하다.

이러한 내용을 바탕으로 작성된 코드 전문은 다음과 같다.

#include <iostream>
#define MAX(a, b) ((a > b) ? a : b)
int n;
int stair[400][3];

int main(){
    std::ios::sync_with_stdio(false);
    std::cin.tie(NULL);
    std::cout.tie(NULL);

    std::cin >> n;
    for(int count = 1; count <= n; count++){
        int num;

        std::cin >> num;
        stair[count][1] += num;
        stair[count][2] += num;
        if(stair[count + 1][2] < stair[count][1]){
            stair[count + 1][2] = stair[count][1];
        }
        if(stair[count + 2][1] < MAX(stair[count][1], stair[count][2])){
            stair[count + 2][1] = MAX(stair[count][1], stair[count][2]);
        }
    }

    std::cout << MAX(stair[n][1], stair[n][2]);
}