파이썬) 백준 알고리즘 | 1351번 : 무한 수열

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

1351번: 무한 수열

백준 1351 '무한 수열' 문제입니다.

피보나치 수열 문제랑 비슷한 거 같아서 재귀로 풀었습니다.

import sys
input = sys.stdin.readline
n, p, q = map(int, input().split())
results = {}

def recursive(m):
    if m == 0:
        return 1
    if m not in results.keys():
        results[m] = recursive(m//p)+recursive(m//q)
    else:
        return results[m]
    return recursive(m//p)+recursive(m//q)
print(recursive(n))