[백준 1351 🥇] 무한 수열

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

1351번: 무한 수열

문제

무한 수열 A는 다음과 같다.

• A0 = 1
• Ai = A⌊i/P⌋ + A⌊i/Q⌋ (i ≥ 1)

N, P와 Q가 주어질 때, AN을 구하는 프로그램을 작성하시오.

입력

첫째 줄에 3개의 정수 N, P, Q가 주어진다.

출력

첫째 줄에 AN을 출력한다.

제한

• 0 ≤ N ≤ 1012
• 2 ≤ P, Q ≤ 109

 

 

문제풀이

import sys

n,p,q=map(int, sys.stdin.readline().split(' '))
# A=[0]*(n+1)
# A[0]=1
# for i in range(1,n+1):
#     A[i]=A[i//p]+A[i//q]

A={}
A[0]=1
def recursion_find_An(num):
    if num in A.keys():
        return A[num]
    A[num]=recursion_find_An(num//p)+recursion_find_An(num//q)
    return A[num]

recursion_find_An(n)
print(A[n])

• 단순히 A[n]을 구할 때까지 이전 값을 모두 계산하는 것은 당연히 시간 초과가 발생한다.(n이 최대 10^12..)
• 그래서 재귀함수를 이용해서 n 이전의 모든 수를 구하지 않고, A[n]을 구하는 데에 필요한 수들만 구해서 최종적으로 A[n]을 구해야 한다.
• 여기서 A라는 딕셔너리를 만들어서, 해당 수가 딕셔너리의 key에 존재할 경우, 즉, 해당 수의 A값이 계산되어 있을 때까지 재귀함수를 타고 들어가서 값을 찾는다.
• 문제의 예제 1번으로 이 과정을 설명해보면 다음과 같다.