백준/실버
[백준 17271번] 리그 오브 레전설 (Small) (C++)
게임개발기원
2024. 4. 26. 17:07
문제링크 : https://www.acmicpc.net/problem/17271
17271번: 리그 오브 레전설 (Small)
규환이는 리그 오브 레전설이라는 게임을 좋아한다. 이 게임에서는 N초의 시간 동안 싸움을 하는데, 규환이가 플레이하는 캐릭터는 A, B 두 가지 스킬을 사용할 수 있다. A 스킬의 시전 시간은 1
www.acmicpc.net
#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값을 나눠주고 출력하도록 해준다.