계단 오르기

• DP 문제를 푸는 순서
  1) 테이블 정의 : D[i]가 어떤 의미인지 정의
  2) 점화식 찾기
  3) 구현

• 해당 문제를 접근하는 2가지 접근
  1) D[i][j] = 연속된 j개의 계단을 밟고 i번째 계단에 올랐을 때 점수의 최대 값
  (단, i번째 계단은 밟아야 함)
  2) D[i] = i번째 계단까지 왔을 때 밟지 않을 계단의 합의 최솟값
  (단, i번째 계단은 밟지 않아야 함)

코드

[ 1번 접근 풀이 ]

#include <string>
#include <iostream>
#include <cmath>
using namespace std;
int v[302];
int d[302][3];
int N;
int main(){
    ios::sync_with_stdio(0);
    cin.tie(0);

    cin >> N;
    for(int i=1;i<=N;i++) cin >> v[i];
    /* 초기값 지정 주의! */
    d[1][2] = 0;
    d[1][1] = v[1];
    d[2][1] = v[2];
    d[2][2] = v[1] + v[2]; 
    /* N=1일때 예외처리 필수 */
    if(N == 1) {
        cout << v[1];
        return 0;
    }
    int flag = 1;
    for(int i=3;i<=N;i++)
    {
        d[i][1] = max(d[i-2][1], d[i-2][2]) + v[i];
        d[i][2] = d[i-1][1] + v[i];
    }
    cout << max(d[N][1], d[N][2]);
    return 0;
}

• key point!
  : 연속된 3개의 계단을 밟을 수 없다
      --> 2차원 배열로 경우의 수를 나눠야 함
• N == 1일때 예외처리

---

[ 2번 접근 설명 ]

• D[i] = i번째 계단까지 왔을 때 밟지 않을 계단의 합의 최솟값
  (단, i번째 계단은 밟지 않아야 함)

• D[i] = min(d[i-2], d[i-3]) + v[i] 라는 점화식이 도출된다.
  : i번째를 밟지 않았다는 것은 i-1은 반드시 밟았고, i-2 나 i-3은 반드시 밟아야 한다!

• 문제를 곧이 곧대로 받아들이지 않고, 반대로 생각하면 다른 점화식이 도출될 수 있다는 것을 기억!