[C++][백준 2579] 계단 오르기 (DP)

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

풀이

n번째 계단을 밟았을 때의 최대 점수를 구하는 방식을 반복하면 된다

 

dp[n]은 n번째 계단을 밟았을 때 최대 점수를 뜻하고, arr[n]은 n번째 계단의 점수라고 치자

 

dp[1] = arr[1]이다

dp[2] = arr[2] + arr[1]이다

dp[3] = arr[3] + arr[2] 또는 arr[3] + arr[1] 둘 중 큰 값이다

dp[4] = arr[4] + arr[3] + arr[1] 또는 arr[4] + arr[2] + arr[1] 둘 중 큰 값이다

dp[5] = arr[5] + arr[4] + arr[2] + arr[1] 또는 arr[5] + arr[3] + arr[2] 또는 arr[5] + arr[3] + arr[1] 중 큰 값이다

 

적어나가다 보면 규칙이 보이는데

(계단 3개를 연속해서 밟을 수 없고, 연속된 2개 이상의 계단을 안 밟을 수 없다)

n번째 계단을 반드시 밟는다면 n - 1번째 계단을 밟거나 밟지 않는 선택지가 주어진다

n - 1번째 계단을 밟느냐 아니냐에 따라 n - 2번재 계단을 밟거나 밟지 않아야 한다

n - 3번째 계단은 n - 1번째 계단을 밟았냐 아니냐에 좌지우지되지 않는다

 

그렇다면 n - 1번째 계단을 밟는 선택지에서의 최대 점수는

arr[n] + arr[n - 1] + (n - 3번째 계단을 밟는 선택지 중 최대 점수)일 것이다

즉, arr[n] + arr[n - 1] + dp[n - 3]이다

 

n - 1번째 계단을 밟지 않는 선택지는 어떨까?

arr[n] + (n - 2번째 계단을 밟는 선택지 중 최대 점수)일 것이다

즉, arr[n] + dp[n - 2]이다

 

따라서 n번째 계단을 밟는 경우 최대 점수는 위 두 경우 중 더 점수가 높은 경우가 될 것이다

 

제출 코드

#include <iostream>
using namespace std;

int arr[301];
int dp[301];

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

    int n, score;
    cin >> n;
    for (int i = 1; i <= n; i++)
        cin >> arr[i];

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

    cout << dp[n];
}