백준 1351번 무한수열

점화식은 나와있으니 구현만 하면 되는데 주의할 점이 있다.

n이 최대 10^12라는점이다.

import sys

n,i,q=map(int,sys.stdin.readline().rstrip().split())
dic={}
def dfs(num):
    if num==0:
        return 1
    if num in dic:
        return dic[num]
    dic[num]=dfs(num//i)+dfs(num//q)
    return dic[num]
print(dfs(n))

해시를 써서 간단히 해결할 수 있다.