[C++][백준 17271] 리그 오브 레전설 (Small)

문제

접근 방법

각 지점에선 A 스킬을 사용하는 법, B 스킬을 사용하는 법 2가지 조합으로 나아갈 수 있다.

A 스킬을 사용하면 1초 뒤 조합의 개수가 늘어난다.
B 스킬을 사용하면 M초 뒤 조합의 개수가 늘어난다.

코드

#include <iostream>
#include <vector>
using namespace std;
#define size N + 1
int N, M;
vector<int> dp;
int main()
{
    ios::sync_with_stdio(0), cin.tie(0);

    cin >> N >> M;

    dp = vector<int>(size);
    dp[0] = 1;

    for (int i = 0; i < size; ++i)
    {
        if (i + 1 < size)
        {
            dp[i + 1] = (dp[i] + dp[i + 1]) % 1000000007;
        }

        if (i + M < size)
        {
            dp[i + M] = (dp[i] + dp[i + M]) % 1000000007;
        }
    }

    cout << dp[N];
    return 0;
}

풀이

다이나믹 프로그래밍을 활용하면 된다.
현재 시점에서의 조합 총합을 다음 시점에 조합 총합에 더해주는 것을 반복하면 가능한 조합의 수를 구할 수 있다.