계단 오르기 2579

문제

접근 방법

규칙에 맞추어 값을 확인해본다.
10
1개이므로 10이 최댓값이다.

10 20
두 개를 합친 30이 최댓값이다.

10 20 15
만약 시작 지점에서 20으로 건널 수 있다면 35가 최대일 것이다.

10 20 15 25
30에 25를 더한 55가 최대이다.

10 20 15 25 10
10을 이어 밟으면 65가 최댓값이다.

10 20 15 25 10 20
25에서 10이 아닌 20을 밟으면 75가 최대이다.

10 20 15 25이 지점을 통해 규칙을 생각해본다.
순서대로 1부터 4라고 할 때 4의 값이 최대가 되려면 3 또는 2의 값을 이어 붙였을 경우의 최댓값을 가져가야 한다.
3까지 누적된 값을 바로 붙였을 경우 문제가 생길 수 있다. 3이 2랑 붙었을 경우를 누적했을 수도 있기 때문이다.
그러한 문제는 1까지 누적된 값과 3과 4를 합쳐서 해결할 수 있다.
2까지 누적된 값을 합치는 건 문제가 없다. 세 개의 계단을 밟는 경우가 아니기 때문이다.

코드

#include <iostream>
#include <vector>
#include <algorithm>
using namespace std;
int main()
{
    ios::sync_with_stdio(0), cin.tie(0);
    int N;
    cin >> N;
    vector<int> dp(N + 1), nums(N + 1);
    for (int i = 1; i <= N; ++i)
        cin >> nums[i];
    dp[1] = nums[1];
    if (N > 1)
    {
        dp[2] = nums[1] + nums[2];
        for (int i = 3; i <= N; ++i)
        {
            dp[i] = max(dp[i - 2], dp[i - 3] + nums[i - 1]) + nums[i];
        }
    }
    cout << dp[N];
    return 0;
}

풀이

연속된 3개를 밟으면 안 된다는 조건을 충족시키기 위한 방법을 생각해내면 해결되는 문제라고 생각된다.
DP 문제치곤 생각보다 좁은 범위의 입력을 받는 문제 같다.