[Silver 3] 2579번 계단 오르기

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

2579번: 계단 오르기

 

이 문제는 Dynamic Programming을 사용해서 해결해야한다.

 

알고리즘은 다음과 같다.

• 계단은 1 step과 2 step으로 이동할 수 있다. 
• dp[0]은 1번째 계단으로 한다. 또한 dp[1]은 2 step으로 이동했을 때와 1step으로 이동했을 때의 최대값으로 한다.
• dp[2]는 1번째 계단에서 2 step으로 이동했을 때와 2번째 계단에서 1step으로 이동했을 때의 최대값으로 한다. 

위 알고리즘을 적용한다면 dp[N]은 max(N번째 계단 + N-2번째 계단, N번째 계단 + N -1 번째 계단 + N-3번째 계단) 이다.

•  N-3이 되는 이유는 연속으로 3번 계단을 밟을 수 없기 때문이다.
• dp의 0, 1, 2번째 요소는 초기 계단을 밟을 수 있는 경우를 모두 저장한 것이다.

 

#include <iostream>

using namespace std;
#define MAX 301

int N;
int stairs[MAX];
int dp[MAX];

int main() {
    cin >> N;

    for(int i=0;i<N;i++) 
        cin >> stairs[i];
    
    dp[0] = stairs[0];
    dp[1] = max(stairs[1],stairs[0]+stairs[1]);
    dp[2] = max(stairs[0] + stairs[2],stairs[1]+stairs[2]);

    for(int i=3;i<N; i++) 
        dp[i] = max(stairs[i] + dp[i-2], stairs[i]+stairs[i-1] +dp[i-3]);

    cout << dp[N-1];
}