[백준] 1351번 > 무한 수열

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

힌트

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

 

---

풀이

문제를 해결하는 점화식은 매우 간단하게 구현할 수 있다. 하지만 초기에 리스트를 통해 dp를 구현하였더니 메모리 초과가 발생하였다. 그래서 dictionary 중에 defaultdict을 사용하여 문제를 해결하였다.

defaultdict은 삽입하지 않은 키값을 호출하더라도 default로 지정되어 있는 딕셔너리이다.

int로 지정해주었기 때문에 삽입하지 않은 키값을 호출하면 기본값 0이 튀어나온다. 이를 재귀형식으로 구현하였다.

 

from collections import defaultdict
import sys
def dp(n):
    if data[n] != 0:
        return data[n]
    data[n] = dp(n // p) + dp(n // q)
    return data[n]
input = sys.stdin.readline
n, p, q = map(int, input().split())
data = defaultdict(int)
data[0] = 1
print(dp(n))