알고리즘 - Python / 백준 - 1737번 : Pibonacci

1737번: Pibonacci (acmicpc.net)

1737번: Pibonacci

 

---

풀이

• 점화식이 다음과 같은 Pibonacci 수를 구하는 문제다.

• 피보나치 수열과 비슷하게 DP로 접근해 풀어 보았다.
• DP[N][K] 배열에서 N은 P[K-N*파이] 로 정의하였다.
• 즉 만약 P[10]을 구하고 싶다면 DP[0][10] = DP[10-0*파이] 를 구하면 되는 것이다.
• 이때 Pibonacci 점화식에 따른 DP 점화식은 DP[N][K] = DP[N+1][K] + DP[N][K-1] 이다.
• 해석하자면 , 만약 DP[0][10] 의 경우 , P[10] 이고 이는 P[9] + P[10-1*파이] 다.
• P[9]는 DP 배열에서 DP[0][10-1] 이고 , P[10-1파이]는 P[0+1][10] 이므로 위 같은 DP 점화식이 나온다.
• 또 , 이 부분에서 시간을 많이 잡아먹었는데 , P[A-B파이] = 1 이 되는 조건은 0 <= A - B파이 <= 파이 이다.
• 이 조건은 처음에 DP 배열의 초기값을 세팅할 때 사용된다.
• 예를 들어 DP[1][5] 의 경우 P[5-1*파이] = P[약 1.8] 이므로 1 이다.
• 이처럼 해당 DP 배열에서 파이만큼 뺀 값이 조건값 사이에 있는지 체크하면서 DP 초기 배열을 세팅해주어야 한다.
• 처음에는 이를 단순하게 3.14로 생각하고 3칸씩 만들어주다가 틀린 답을 도출하였다.
• 파이는 분명하게 뒤쪽에 소수점이 존재하므로 , 어느 순간 소수점이 누적되어 3칸씩 밀리지 않는 구간이 존재한다.
• 이를 math 라이브러리의 math.pi를 통해 해결하였다.

 

 

 

 

N = 13 일 때의 DP배열

 

 

 

 

N = 10 일때 정답 DP 배열 DP[0][10] = 19

 

 

 

 

import sys
import math
n = int(sys.stdin.readline())
dp = [[0 for i in range(n + 1)] for t in range((n // 3) + 1)]
line = [4]
if n < 4:
    print(1)
else:
    check = 1
    dp[0][1] , dp[0][0] , dp[0][2], dp[0][3] = 1,1,1,1
    for k in range(4,n+1):
        if k - check*math.pi < math.pi:
            dp[check][k] = 1
        else:
            check += 1
            line.append(k)
            dp[check][k] = 1

    for k in range(len(line)-1,-1,-1):
        for o in range(line[k],n+1):
            dp[k][o] = dp[k+1][o] + dp[k][o-1]

    print(dp[0][n]%1000000000000000000)

---