BOJ 2579 : 계단 오르기

먼저, 입력받은 값은 dp[0][n]에, 계산한 합은 dp[1][n]에 넣는다고 한다.

조건에 의해 마지막 계단은 꼭 밟아야 하므로, 상황을 2가지로 함축해 볼 수 있다.

 

1) 마지막 계단 과 그 전 계단을 밟을 경우

2) 마지막 계단과 그 전전 계단을 밟을 경우.

 

마지막 계단을 dp[0][n] 이라고 했을때, 연속된 3개의 계단을 밟을 수 없으므로,

 

1번의 상황에서는 dp[0][n-3]과 dp[0][n-1]을 밟았을 것이다. 즉,

dp[1][n] = dp[0][n] + dp[0][n-1] + dp[1][n-3]

 

2번의 상황에서는 dp[n-2] 만 밟고 올라왔을 것이다. 이때에는 dp[1][n-2] 까지는 n-2 일때 계산이 되어있을 것이므로

dp[1][n] = dp[0][n] + dp[1][n-2]

 

이 두개의 max 값을 비교하면 된다......

 

또한, n = 0~2일때는

dp[0][0] = dp[1][0]

dp[0][1] = dp[0][0] + dp[0][1]

dp[0][2] = dp[0][2]+max(dp[0][0], dp[0][1])

이다.

 

<소스코드>

#include<iostream>
#include<algorithm>
using namespace std;
int main() {
    int dp[2][301] = { 0, };
    int n = 0;
    cin >> n;
    for (int i = 0; i <n; i++)
        cin >> dp[0][i];
    dp[1][0] = dp[0][0];
    dp[1][1] = dp[0][0] + dp[0][1];
    dp[1][2] = max(dp[0][0] + dp[0][2], dp[0][1]+dp[0][2]);
    for (int i = 3; i < n; i++) 
        dp[1][i] = max(dp[0][i] + dp[0][i - 1] + dp[1][i - 3], dp[0][i] + dp[1][i - 2]);
    cout << dp[1][n - 1];
}

 

문제 :

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

2579번: 계단 오르기