[백준 2579번] 계단 오르기 (C++)

https://www.acmicpc.net/problem/2579

2579번: 계단 오르기

---

계단 오르기 문제는 다이나믹 프로그래밍을 이용하여 해결할 수 있습니다.

다이나믹 프로그래밍은 테이블 정의, 점화식 작성, 초기값 정하기으로 구분할 수 있습니다.

1. 테이블 정의
   • d[n][i]은 n번째 계단까지의 최대 점수를 의미합니다. (i는 마지막에 연속된 계단의 개수)
   • 연속된 세 개의 계단을 밟지 않아야 된다는 조건이 있기 때문에 2차원 배열로 구성하였습니다.
2. 점화식 작성
   1. d[n][1]은 연속된 계단의 개수가 1개 이므로, 두칸 전의 계단에서 올라온 경우입니다.
   2. 두 칸 전의 계단은 d[n - 2][1], d[n - 2][2]로 구분됩니다. 따라서 두 점수중 더 높은 것을 선택하면 됩니다.
      d[n][1] = s[n] + max(d[n - 2][1], d[n - 2][2]입니다. (단, s[i]는 i번째 계단의 점수입니다.)
   3. d[n][2]는 한칸 전의 계단에서 올라온 경우입니다.
      단, d[n - 1][2]는 이미 2개의 계단을 연속적으로 밟았으므로 n번째 계단을 밟을 수 없습니다. 따라서 d[n][2] = s[n] + d[n][1]입니다. 
3. 초기값 정하기
   1. 점화식에 한칸 전과 두칸 전의 점수가 필요하므로, d[1][0], d[1][1], d[2][1], d[2][2]의 값을 정해주면 됩니다.

아래는 Bottom-Up 방식의 다이나믹 프로그래밍 코드입니다.

#include <bits/stdc++.h>
using namespace std;

int s[301];    // 각 계단의 점수
int d[301][3];    // d[i] : i번째 계단까지 올라갈 때, 얻을 수 있는 최대 점수와 마지막에 연속된 계단의 개수
int main(){
    ios::sync_with_stdio(0);
    cin.tie(0);
    int n; cin >> n;
    for(int i = 1; i <= n; i++) cin >> s[i];
    
    d[1][1] = s[1]; 
    d[2][1] = s[2]; d[2][2] = s[1] + s[2];
    for(int i = 3; i <= n; i++){
        d[i][2] = s[i] + d[i - 1][1];    // 한 칸 전에서 오는 경우
        d[i][1] = s[i] + max(d[i - 2][1], d[i - 2][2]); // 두 칸 전에서 오는 경우
    }
    cout << max(d[n][1], d[n][2]) << "\n";
}