99클럽 코테 스터디 15일차 TIL + DP

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

import sys
input = sys.stdin.readline
mod = 1000000007

n, m = map(int, input().split())

dp = [1] * (n+1)

for i in range(m, n+1):
    dp[i] = (dp[i-1] + dp[i-m]) % mod

print(dp[n])

• A스킬 시전시간은 1초, B스킬 시전시간은 m초 이기 때문에 n이 m보다 작을 때에는 무조건 A스킬만 사용할 수 있다.
  • m초 이하일 때에는 A스킬만 사용하기 때문에 경우의 수는 1 이다. (dp[i] = dp[i-1] = 1)
  • m초 이상일 때에는 A스킬과 B스킬을 함께 사용할 수 있다.
    • t초 일 때
      • t-1초까지 스킬 쓴 상태에서 A스킬 사용 가능
      • t-m초까지 스킬 쓴 상태에서 B스킬 사용 가능
      • dp[t] = dp[t-1] + dp[t-m]
• 점화식 생각하기가 어려우면 n=1 부터 경우의 수를 써내려가며 생각해봐야 한다....