(WIP) 백준 알고리즘 17272. 리그 오브 레전설

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

N 이 너무 커서 주어진 제약사항 안에서 DP 로 풀 수 없는 듯?
다른 방법을 찾아야 할 듯? M 이 100 이하의 자연수라는 점이 단서일까?

제약사항
첫 번째 줄에 싸움 시간 N과 B 스킬의 시전 시간 M이 주어진다. (N은 10^18 이하의 자연수, M은 2 이상 100 이하의 자연수)
메모리 256MB, recursive call limit 1000

# https://www.acmicpc.net/problem/17272
# m: B스킬의 시전 시간
# n: 싸움 시간

# DP (memoization): Recursion Error. call depth is limited upto 1000 in acmicpc
def f(n, m):
    def f_(n, memo):
        # 1을 선택하거나 m 을 선택할 수 있음
        if n in memo: return memo[n]
        if n<0: return 0
        if n==0: return 1

        ans = f_(n-1, memo) + f_(n-m, memo)
        memo[n] = ans
        return ans % 1000000007

    return f_(n, {})

# DP (tabluation): memory limit error. 256MB in this problem
def f(n, m):
    dp = [0 for _ in range(n + 1)]
    dp[0] = 1
    for i in range(1, n+1):
        dp[i] = dp[i-1]
        if i-m >= 0:
            dp[i] += dp[i-m]

    return dp[n] % 1000000007

assert f(4,2) == 5
assert f(3,2) == 3
if __name__ == '__main__':
    N, M = list(map(int, input().split()))
    ans = f(N, M)
    print (ans)