[Python] 백준 1351번: 무한 수열

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

1351번: 무한 수열

• 0 ≤ N ≤ 10^12
• 2 ≤ P, Q ≤ 10^9

1. 범위가 위와같은데 시간제한은 2초이므로 일반 배열로 dp를 할경우 배열의 길이를 N만큼 잡아야하는데 이러면 시간초과가 난다.

2. n값을 p, q로 나눈 몫으로 top-down 방식으로 진행한다. 

3. 메모이제이션은 배열이아닌 사전을 이용한다. 계속 트리형식으로 나누어 지기때문에 시간복잡도는 O(logN)으로 무난히 통과한다.

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

def go(k):
    i, j = k // p, k // q
    if dic.get(k, 0):
        return dic[k]
    if not dic.get(i, 0):
        dic[i] = go(i)
    if not dic.get(j, 0):
        dic[j] = go(j)
    return dic[i] + dic[j]

print(go(n))