(Python/🥇5)백준알고리즘 1351번:무한 수열

문제 바로가기 

무한수열

 

문제:

무한 수열 A는 다음과 같다. A0 = 1

Ai = A⌊i/P⌋ + A⌊i/Q⌋ (i ≥ 1)

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

입력:

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

출력:

첫째 줄에 AN을 출력한다.

 

 

import sys
from collections import defaultdict

sys.stdin = open('/Users/song/Desktop/Python/Python/h.txt', 'r')

n, p, q = map(int,sys.stdin.readline().split(" "))
dp = defaultdict(int)
dp[0] = 1

def dfs(n):
    if dp[n] != 0:
        return dp[n]
    dp[n] = dfs(n // p) + dfs(n // q)
    return dp[n]
print(dfs(n))

 

재귀? dp 문제 n이 너무커서 테이블 선언 안 하고 defalutdict을 사용했다.