[BOJ/Python] 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 ≤ 10^12
• 2 ≤ P, Q ≤ 10^9

예제 입력 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를 넘지 않는 가장 큰 정수이다.

 

---

풀이

 

import sys
 
n,p,q = map(int,sys.stdin.readline().split())
 
n_dict = {0:1}
 
def find(num):
    if num not in n_dict:
        n_dict[num] = find(num//p) + find(num//q)
    
    return n_dict[num]
    
print(find(n))

1. 딕셔너리 자료형을 이용한다. A0 = 1이므로, n_dict[0] = 1인 딕셔너리를 생성한다.
2. 함수 find의 경우, 만약 찾는 값이 n_dict에 존재한다면 그 값을 반환한다.
3. 존재하지 않는다면, 재귀를 이용하여 값을 찾아 그 값을 반환한다.

• 만약 딕셔너리를 이용하지 않고, 리스트를 이용한다면 n의 범위가 최대 10^12까지이므로, 리스트의 크기가 최대 10^12까지 생성되므로 적합하지 않다.
• num//p의 경우 num을 p로 나눈 몫을 반환하는데, ⌊x⌋는 x를 넘지 않는 가장 큰 정수이므로 같은 값을 가진다.