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

문제 링크 : https://www.acmicpc.net/problem/2579

2579번: 계단 오르기

풀이

다이나믹 프로그래밍을 이용하여 풀이하였다.

2차원 배열을 사용해서 arr[x][0]은 x번째 계단을 밟고 이전에 연속적인 계단을 밟지 않았을 경우, 즉 x-2번째 계단을 밟았을 때로, arr[x][1]은 x번째 계단을 밟고 이전에 연속적인 계단을 밟았을 경우, 즉 x-1번째 계단을 밟았을 때이다.

마지막으로 다이나믹 프로그래밍을 진행할 때 x-2가 인덱스일 때의 값이 필요하므로 초기값으로 인덱스가 0일 때와 1일 때를 설정해 준다.

#include <iostream>

using namespace std;

int arr[302][4];
int v[302];
int n;

int main() {
    ios::sync_with_stdio(0);  
    cin.tie(0);
    cout.tie(0);

    cin >> n;
    for(int i = 0; i < n; i++){
        cin >> v[i];
    }
    arr[0][0] = v[0];
    arr[0][1] = v[0];
    arr[1][0] = v[1];
    arr[1][1] = v[0] + v[1];

    for(int i = 2; i < n; i++){
        arr[i][0] = max(arr[i-2][0], arr[i-2][1]) + v[i];
        arr[i][1] = arr[i-1][0] + v[i];
    }
    cout << max(arr[n-1][0], arr[n-1][1]);
}