백준 1351 - 무한 수열 (Python)

문제

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

1351번: 무한 수열

풀이

n, p, q = map(int,input().split())
memo = {}
memo[0] = 1

def a(i):
    if i not in memo:
        memo[i] = a(i//p) + a(i//q)
    return memo[i]

print(a(n))

 

 n의 크기가 0 ≤ N ≤ 10^12 로 매우 크므로 DP 중 tabulation 방식으로는 풀수가 없었다.  크기가 10^12인 배열을 생성하니 그냥 오류를 뱉어 버리더라...

 

그래서 딕셔너리와 재귀함수를 이용하여 memoization 방식으로 구현해주었다.

재귀함수를 통해 a(i) 를 구하는 과정에서 a(i//p)와 a(i//q)를 호출하게 되고 각 호출에서 이미 memo 에 저장된 값이 있으면 해당 값을 바로 반환하고 아니면 직접 계산하여 memo에 저장한 뒤 반환해준다.