1737 - Pibonacci
문제
피보나치(Fibonacci) 수열은 매우 유명한 수열로 그 점화식은 F[i]=F[i-1]+F[i-2]와 같이 표현된다. 우리는 이와 같은 수열을 살짝 변경한 피보나치(Pibonacci) 수열에 대해 살펴보자. 피보나치 수열의 점화식은 아래와 같다.
- P[n] = 1 (0 ≤ n ≤ π)
- P[n] = P[n-1] + P[n-π] (그 외)
주의할 것은 n이 꼭 정수일 필요는 없다는 것이다. 즉, P[n-π] = P[n-π-1]+P[n-π-π]와 같은 식으로 계산을 해 주어야 한다.
자연수로 n이 주어졌을 때, P[n]을 구하는 프로그램을 작성하시오.
코드
import math
import sys
sys.setrecursionlimit(10**6)
def pibonacci(num):
if 0 <= num <= math.pi:
return 1
if num in dp:
return dp[num]
dp[num] = pibonacci(num - 1) + pibonacci(num - math.pi)
return dp[num] % 1000000000000000000
N = int(input())
dp = dict()
print(pibonacci(N))한마디
다른 피보나치 문제들처럼 리스트로 접근했는데, 파이 때문에 인덱스 처리를 해주지 못했다. 고민 끝에 딕셔너리를 사용했더니 한 번에 해결할 수 있었다.
