[Silver I] 리그 오브 레전설 (Small) - 17271 (DP)

[Silver I] 리그 오브 레전설 (Small) - 17271

규환이는 리그 오브 레전설이라는 게임을 좋아한다. 이 게임에서는 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로 나눈 나머지 값을 출력한다.

 풀이 방법

dp 알고리즘을 사용하여 풀 수 있다.

A는 무조건 1초 B는 M초 이므로, dp의 인덱스를 초라고 생각한다.

dp[0] : 0초는 A,B를 사용하지 않은 경우의 수 1개 이므로 dp[0] = 1을 저장.

 

바텀업 방식을 사용하여 문제를 해결한다.

dp[i]에 올 수 있는 값으로 dp[i] += dp[i-A] 와 dp[i-B]를 통해 이전 시간의 스킬 조합의 수를 구해줄 수 있다.

단, B는 i보다 작거나 같아야 -1초 이하로 가지 않기 때문에 범위 설정을 해줘야한다.

INF = 1000000007
n, m = map(int,input().split())
dp = [0] * (n+1)
dp[0] = 1 # 0번 스킬 쓰는 경우 : 한 번
for i in range(1, n+1):
    dp[i] = dp[i-1] % INF
    if i >= m:
      dp[i] += dp[i-m] % INF
print(dp[n] % INF)