[Algorithm] 백준 2579 - 계단 오르기

문제

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

 

풀이

DP로 문제를 풀면 된다.

DP로 풀기 위해 점화식을 먼저 찾아야하는데 Step(int k)는 k번째 계단에서 최대 점수라 하자.

계단을 오르는 규칙은 다음과 같다.

• 한 번에 하나의 계단 or 두개의 계단을 오를 수 있음
• 연속된 3개의 계단을 밟아서는 안됨

이를 바탕으로 k번째 계단을 밟는 경우의 수를 생각해보면

1. 하나의 계단을 연속으로 밟는 경우
2. 건너뛰기로 밟는 경우

1번의 경우 건너뛰기->하나 밟기 -> 마지막 밟기가 되며 연속된 계단을 2개까지 밟으므로 규칙을 준수한다.

2번은 건너뛰기->마지막 밟기가 된다.

!! 건너뛰기->밟기->밟기->마지막 밟기는 연속 3번이므로 성립 X

 

위의 결과를 바탕으로 점화식을 작성하면 2가지 경우의 수 중 최대인 경우를 택하면 된다.

•  Step(k) = max(Step(k-3) + Score[i-1] + Score[i], Step(k-2) + Score[i]);

코드

#include <bits/stdc++.h>
using namespace std;

int step[301];
int dp[301];


int main()
{
    int n;
    cin >> n;
    for(int i=1; i<=n; i++)
        cin >> step[i];
    dp[1] = step[1];
    dp[2] = dp[1]+step[2];
    for(int i=3; i<=n; i++)
        dp[i] = max(dp[i-3]+step[i-1]+step[i], dp[i-2]+step[i]);
    cout << dp[n];
}