알고리즘/BOJ

[BOJ] 1351. 무한 수열

ㅣlㅣl 2024. 6. 25. 17:31

문제

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))

 

 


 

제출 결과