백준 온라인 저지, 자료구조 / 1351번: 무한수열 (파이썬 / , 백준 골드문제)

문제

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

• A₀ = 1
• A_i = A_⌊i/P⌋ + A_⌊i/Q⌋ (i ≥ 1)

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

입력

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

출력

첫째 줄에 A_N을 출력한다.

제한

• 0 ≤ N ≤ 10¹²
• 2 ≤ P, Q ≤ 10⁹

예제 입력 1

7 2 3

예제 출력 1

7

예제 입력 2

0 2 3

예제 출력 2

1

예제 입력 3

10000000 3 3

예제 출력 3

32768

예제 입력 4

256 2 4

예제 출력 4

89

예제 입력 5

1 1000000 1000000

예제 출력 5

2

힌트

⌊x⌋는 x를 넘지 않는 가장 큰 정수이다.

접근 방법

- 딕셔너리를 활용해 트리구조를 구현하여 다이나믹프로그래밍을 동작시켜 An을 구한다.

코드

# https://www.acmicpc.net/problem/1351
# 접근방법
# 딕셔너리를 활용해 트리구조를 구현하여 다이나믹프로그래밍을 동작시켜 An을 구한다.
def dfs(x):
    if x in idx:
        return tree[x]
    value = dfs(x//p) + dfs(x//q)
    tree[x] = value
    idx.add(x)
    return value

n, p, q = map(int, input().split())
tree = {}
tree[0] = 1
idx = set()
idx.add(0)
print(dfs(n))