[BOJ] 1351. 무한 수열

문제

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

• 이것도 처음에 뭔 말이지..? 싶었다

이 조건을 제대로 풀기만 하면 됨

• 현재 인덱스를 P와 Q로 나눈 것의 "내림값" 인덱스의 합
• A_0 = 1

---

 

주요 아이디어

• 전형적인 DP 문제
• 탑다운 방식으로 풀어보자!

 

---

 

코드 구현 (Python 3)

 

from collections import defaultdict

# 수열 n번째 반환
def dp(n):
    # 저장되어 있는 값이면
    if data[n] != 0:
        return data[n]

    data[n] = dp(n // p) + dp(n // q)
    return data[n]


n, p, q = map(int, input().split())
data = defaultdict(int)
data[0] = 1 # 초기값 작성

print(dp(n))

 

 

---

 

제출 결과