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

백준2579 계단 오르기

계단 오르기 문제는 동적 프로그래밍 문제를 연습할 수 있는 좋은 유형이다.

하지만 생각해봐야 할 것이 좀 많다.

우선, 새로운 계단에 오를 때에는 두 가지 경우의 수가 존재한다.

1. 한 번에 두 계단을 올라서 나한테 오는 경우 (연속하여 한 개의 계단을 밟고 오는 경우)
   1. 이 경우에는 한 번에 두 칸을 올라오는 것이기 때문에 현재 새로운 계단 i 를 기준으로 i-1번째 계단은 밟지 않고 올라오는 경우이다.
   2. 따라서 i-2 번째 계단의 값을 살펴봐야 한다. i-2 번째 계단은 두 가지 값을 가지고 있다.
      1. i-2 번째 계단에 도착할 때 연속하여 두 칸을 걸어 올라왔는지 ,한 칸을 건너뛰고 올라왔는지에 따라 두 가지 값을 가지고 있다.
      2. 두 값 중 더 큰 값을 선택해야 한다.
2. 두 번째 경우는 연속하여 두 개의 계단을 걸어 올라오는 경우이다. (건너뛰지 않고 올라옴)
   1. 두 계단을 걸어 올라오는 것이기 때문에 i 번째 계단에 올라오기 전 마지막으로 밟는 계단은 i-1번째 계단이다.
   2. i-1 번째 계단 또한 두 가지 값을 가진다.
      1. i-1 번째 계단에 도착할 때 연속하여 두 칸을 걸어 올라왔는지, 한 칸을 건너뛰고 올라왔는지에 따라 두 가지 값을 가지고 있다.
      2. 연속하여 두 칸을 걸어 i-1 번째 계단에 올라왔을 경우 ‘연속한 세 개의 계단을 오를 수 없다’ 라는 규칙에 따라 i 번째 계단을 밟을 수 없게 된다.
      3. 따라서 i-1번째 계단에서 값을 고를 때는 한 칸을 건너 뛰고 i-1 번째 계단을 밟은 경우만 가정해야 한다.

    #include <iostream>
   
    using namespace std;
   
    int stairs[301];
   
    int main(){
        int N;
        cin >> N;
        for(int i=1;i<=N;i++){
            cin >> stairs[i];
        }
        int answers[301][3];
        answers[1][1] = stairs[1];
        answers[1][2] = 0 ;
        answers[2][1] = stairs[2];
        answers[2][2] = stairs[1] + stairs[2];
           
        for(int i=3;i<=N;i++){
            // 한 번에 두 계단을 올라서 나한테 오는 경우 (연속하여 한 개의 계단을 밟고 나한테 오는 경우)
            answers[i][1] = max(answers[i-2][1], answers[i-2][2]) + stairs[i];
               
            // 한 번에 한 계단씩 올라서 나한테 오는 경우 (연속하여 두 개의 계단을 밟고 나한테 오는 경우)
            answers[i][2] = answers[i-1][1] + stairs[i];
        }
        cout << max(answers[N][1],answers[N][2]) << "\n";
           
    }