[C++] BOJ 2579 / DP (계단 오르기, 점화식 2차원 배열 접근)

코드

#include <iostream>
#include <algorithm>
using namespace std;
int stairs[301];
int arr[301][2];
int main() {
    ios::sync_with_stdio(0);
    cin.tie(0);
    int n;
    cin >> n;
    for(int i=0;i<n;i++) {
        cin >> stairs[i];
    }
    arr[0][1] = stairs[0];
    arr[1][2] = arr[0][1] + stairs[1];
    arr[1][1] = stairs[1];
    for(int i=2;i<n;i++) {
        arr[i][1] = max(arr[i-2][1], arr[i-2][2]) + stairs[i];
        arr[i][2] = arr[i-1][1] + stairs[i];
    }
    cout << max(arr[n-1][1], arr[n-1][2]);
}

 

코드 분석

점화식을 세울 때, 2차원 배열 arr[][] 을 사용하였다.

arr[i][1] => 1칸 째에 i번 계단을 밟았을 때의 최대 점수

arr[i][2] => 2칸 째에 i번 계단을 밟았을 때의 최대 점수

 

점화식

arr[i][1] = max(arr[i-2][1], arr[i-2][2]) + stairs[i]

arr[i][2] = arr[i-1][1] + stairs[i]