[백준] 1351번 무한수열 - 파이썬/재귀

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

N,P,Q = map(int,input().split())

def dfs(x,P,Q):

    before = int(x / P)
    after = int(x / Q)
    if x==0:
        return 1

    else:
        return dfs(before,P,Q)+dfs(after,P,Q)


print(dfs(N,P,Q))

백준에서는 해시에 분류되어있는 문제이다.

재귀문제인데 숫자 범위가 커서 그냥 재귀로 풀면 메모리 초과가 발생한다.

재귀에서 구한 값을 딕셔너리에 저장해서 이미 구한 값은 꺼내오는 식으로 통과할 수 있다.