BOJ 2579번 계단 오르기

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

github : https://github.com/junho0956/Algorithm/blob/master/2579/2579/%EC%86%8C%EC%8A%A4.cpp

 

사실 문제의 점화식을 세우는 과정은 어렵지 않은데

.. 재귀로 짜볼려다가 계속 틀려버렸다

포스팅한후에 다시 고민해봐야겠다 ..

 

점화식은 다음과 같다

현재 계단을 올 수 있는 경우는

1. 전 계단을 밟고 온 경우

2. 전 계단을 밟지 않은 경우

 

1. 전 계단을 밟고 온 경우 전전은 못 밟았기 때문에 전전전 까지의 최댓값을 알고 있으면 된다.

2. 전 계단을 밟지 않은 경우 전전까지는 밟고 온 것이기 때문에 전전 계단에 대한 최댓값을 알고 있으면 된다.

 

#include <iostream>
#include <algorithm>
#include <math.h>
#include <cstring>
using namespace std;
typedef long long ll;
 
int dp[301];
int arr[301];
int N;
 
int main() {
    ios::sync_with_stdio(0), cin.tie(0);
 
    cin >> N;
    for (int i = 1; i <= N; i++) cin >> arr[i];
 
    dp[1] = arr[1];
    dp[2] = arr[1] + arr[2];
    dp[3] = max(arr[1] + arr[3], arr[2] + arr[3]);
    for (int i = 4; i <= N; i++) {
        dp[i] = max(dp[i - 3] + arr[i - 2] + arr[i], dp[i - 3] + arr[i - 1] + arr[i]);
    }
    
    cout << dp[N];
 
    return 0;
}