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

문제링크 : https://www.acmicpc.net/problem/17271

17271번: 리그 오브 레전설 (Small)

#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef pair<int, int> pii;
const int MAX = INT_MAX;

int N, M;
int dp[10001];
const int MOD = 1000000007;

int main()
{
    ios_base::sync_with_stdio(0); 
	cin.tie(0);

    cin >> N >> M;
    dp[0]=1;

    for(int i=1; i<=N; i++)
    {
        dp[i] = dp[i-1]; //1초짜리
        if(i >= M) dp[i] = (dp[i] + dp[i-M])%MOD; //1초짜리 + M초짜리
    }
    cout << dp[N];

    return 0;
}

 

간단한 dp 문제이다.

 

해당 문제에서 고려해야할 부분은 1초짜리와 M초짜리 이렇게 2가지이다.

기본적으로 1초짜리를 계속 갱신해주고,

M초짜리도 갱신이 가능해졌을 때 기존 1초짜리 경우의 수 + M초짜리 경우의 수를 넣어준다.

 

그리고 주어진 조건에 따라 1000000007값을 나눠주고 출력하도록 해준다.