99클럽 코테 스터디 15일차 TIL + 리그 오브 레전설 (Small) DP

문제

규환이는 리그 오브 레전설이라는 게임을 좋아한다. 이 게임에서는 N초의 시간 동안 싸움을 하는데, 규환이가 플레이하는 캐릭터는 A, B 두 가지 스킬을 사용할 수 있다.  A 스킬의 시전 시간은 1초고, B 스킬의 시전 시간은 M초이다. 규환이는 다양한 스킬 조합을 원하기 때문에 가능한 모든 스킬 조합을 알아보고 싶어 한다. 단, 시전 시간 동안은 다른 스킬을 사용할 수 없으며, 스킬을 안 쓰고 있는 시간은 없어야 한다.

예를 들어, N이 4초이고, M이 2초이면 가능한 스킬 조합은 AAAA, AAB, ABA, BAA, BB로 5가지가 가능하다.

 

입력

첫 번째 줄에 싸움 시간 N과 B 스킬의 시전 시간 M이 주어진다. (N은 10,000 이하의 자연수, M은 2 이상 100 이하의 자연수)

출력

가능한 조합의 수를 1,000,000,007로 나눈 나머지 값을 출력한다.

 

---

풀이

import sys
input = sys.stdin.readline

N, M = map(int, input().split())
mod = 1000000007
dp = [0]*(N+1)
dp[0] = 1

for i in range(1, N+1):
    dp[i] = dp[i-1]
    if i >= M:
        dp[i] += dp[i-M]
    dp[i] %= mod
print(dp[N])

dp문제 max만 보다가 요렇게는 또,,

 

mod를 마지막에 해야한다는 점~ 기억기억

 

 

문제 출처

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