무한 수열[백준 1351]

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

 

def dpq(n, p, q, memo):
    if n == 0:
        return 1
    if n in memo:        return memo[n]
    pid = n // p
    qid = n // q
    memo[n] = dpq(pid, p, q, memo) + dpq(qid, p, q, memo)
    
    return memo[n]
n, p, q = map(int, input().split())
memo = {}
print(dpq(n, p, q, memo))
print(memo)