[백준] 1351번: 무한 수열

문제

백준 - 1351번: 무한 수열

분석

무한 수열 A는 다음과 같다.
A0 = 1
Ai = A⌊i/P⌋ + A⌊i/Q⌋ (i ≥ 1)
N, P와 Q가 주어질 때, AN을 구하는 문제이다.

문제를 보고 바로 DP방식이 떠올랐고 정의된 식에 의해서 코드를 짰다.
그런데 N은 최대 10^12이므로 바텀업 방식(for 문)의 다이나믹 프로그래밍을 썼을 경우에 시간초과가 나게 된다. 따라서 더 효율적인 필요한 숫자만 계산하는 탑다운 방식(재귀)을 사용해야한다.

탑 다운 방식을 쓰는데 저장공간을 10^12만큼 할 수 없기 때문에 딕셔너리를 사용한다. defaultdict로 0을 기본적으로 갖게하여 키 에러가 없게 한다.
그리고 참고하는 값이 0이 아니라면 계산된 적 있으므로 바로 return해주고 그게 아니라면 계산 결과를 저장하고 return해준다.

코드

해결언어 : Python

import sys
input = sys.stdin.readline

from collections import defaultdict
n, p, q = map(int, input().split())
A = defaultdict(int)
A[0] = 1

def memoization(i):
    if A[i] != 0:
        return A[i]
    A[i] = memoization(i//p)+memoization(i//q)
    return A[i]
print(memoization(n))

끝으로..

항상 바텀업 방식으로만 풀어왔는데 때에 따라서는 탑다운 방식이 필요하다는 것을 이 문제를 통해 느꼈다.