[Python/BOJ] 1737. Pibonacci

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

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]을 구하는 프로그램을 작성하시오.

입력

첫째 줄에 자연수 n(1 ≤ n ≤ 1,000)이 주어진다.

출력

첫째 줄에 P[n]을 출력한다. 값이 매우 커질 수 있으므로 1,000,000,000,000,000,000으로 나눈 나머지를 출력한다.

풀이

Code

import sys
from math import pi
input = sys.stdin.readline

# 6. 자연수가 아닌 실수부를 처리하기 위한 함수 정의
def check(num) :
    # 6-1. 1번 점화식에 해당할 경우 결과값 리턴 (종료 조건)
    if 0 <= num <= pi :
        return 1
    # 6-2. 인자로 받은 수의 출력값 구하기
    try :
        # 딕셔너리에 해당 key가 있을 경우 (이미 계산이 된 경우)
        num = float_dp[num - 1] + float_dp[num - pi]
    except :
        # 딕셔너리에 해당 key가 없을 경우 (계산된 적이 없는 경우)
        # 딕셔너리에 해당 key와 value 값 입력
        float_dp[num - 1], float_dp[num - pi] = check(num - 1), check(num - pi)
        num = float_dp[num - 1] + float_dp[num - pi]
    return num

n = int(input())
# 1. int 형 dp 생성
int_dp = [0] * (n+1) if n > 3 else [0] * 4
# 2. int 형 dp의 초기값 설정
int_dp[1], int_dp[2], int_dp[3] = 1, 1, 1
# 3. float 형 dp 생성
float_dp = dict()
# 4. float 형 dp의 초기값 설정
float_dp[4-pi], float_dp[5-pi], float_dp[6-pi] = 1, 1, 1
m = 1000000000000000000
# 5.
for i in range(4, n+1) :
    # 5-1. 점화식에 따른 dp 처리 -> 자연수가 아닌 실수부는 따로 처리
    int_dp[i] = (int_dp[i-1] + check(i - pi)) % m
# 7. 결과 출력
print(int_dp[n])