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

문제

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

• 설명: A 스킬이 $1$초, B 스킬이 $M$초 걸릴 때 $N$초 동안 가능한 스킬 조합의 수를 구하여라

풀이

• N초 동안 가능한 스킬 조합의 수는 아래의 합과 같다
  • $(N - 1)$초 동안 가능한 스킬 조합에 A 스킬을 1번 더 쓰거나
  • $(N - M)$초 동안 가능한 스킬 조합에 B 스킬을 1번 더 쓰거나
• 따라서 DP를 사용하여 문제를 풀어준다.

오늘의 회고

• 피보나치에서 한 단계 나아간 대표적인 DP 문제이다!
• 문제 번호가 회문이다!

Code

MOD = 1_000_000_007

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

dp = [1]
for i in range(1, n + 1):
    dp.append(dp[i - 1])
    if i >= m:
        dp[i] += dp[i - m]
    dp[i] %= MOD

print(dp[n])