728x90
반응형
문제 바로가기
문제:
무한 수열 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을 사용했다.
반응형
댓글