[백준 1737] Pibonacci

1737번: Pibonacci

알고리즘 : DP

난이도 : 골드Ⅳ

 

1. 문제요약

• Fibonacci 수열을 변형한 Pibonacci 수열은 다음과 같다.
  
  • P[n] = 1 (0 ≤ n ≤ π)
  • P[n] = P[n-1] + P[n-π] (그 외)
• 1000이하의 자연수 n이 주어질 때, P[n]을 출력하는 프로그램을 작성한다. 다만 값이 너무 커지는 것을 방지하기 위해 1000,000,000,000,000,000로 나눈 나머지를 출력하도록 한다.

2. 아이디어

• 예를들어 P[10] = P[9] + P[10 - π]이고, P[10 - π] = P[9 - π] + P[10 - π*2]이며, P[10 - π*2] = P[9 - π*2] + P[10 - π*3]이고 여기서 P[10 - π*3] = 1이다.
• P[10]을 구하기 위해 필요한 값들 중 P[9], P[9 - π], P[9 - π*2] 는 P[9]를 구할때 필요한 값이므로 DP를 위한 점화식을 만들때는 이 값들은 이미 알고 있다고 가정해도 된다.
• 즉, P[n]을 구하기 위해서는 P[n - π], P[n - π*2], ... ,P[n - π*k]의 k개의 값을 추가로 알아야 한다. (여기서 k는 n을 π로 나눈 몫이다.)
• 따라서 주어진 n에 대하여 n+1의 크기인 리스트 pibo를 만들고, 이 리스트의 i번째 원소는 다시 int[ i / π ] + 1의 크기를 갖는 리스트가 되도록 자료구조를 만든다. 이 자료구조를 DP로 채워나가면 구하는 답을 얻을 수 있다.
  (n = 10이면 리스트 pibo는 [[1], [1], [1], [1], [2, 1], [3, 1], [4, 1], [6, 2, 1], [9, 3, 1], [13, 4, 1], [19, 6, 2, 1]]이 된다.)

3. 구현과정

• math 라이브러리로부터 pi를 import하여 사용한다.
• n을 입력받고, 크기 n+1, i번째 원소는 길이 int(i/pi)+1인 리스트인 리스트 pibo를 만들고 0으로 채워준다.
• pibo[0][-1]에 1을 저장한다. 이 값은 P[0]을 의미한다.
• 이제 0부터 n까지 i로 순회하면서 pibo리스트를 채워줘야 한다.
• 우선 pibo[i][-1]에 1을 저장한다. 이 값은 P[n]에서 π를 뺄 수 있을만큼 뺀 P[n - π*k]의 값을 의미한다.
• 이제 pibo의 i번째 원소인 pibo[i] 리스트를 채워줘야 한다.
• pibo[i][-1]에는 이미 1을 저장했으므로 0부터 len(pibo[i]) - 2까지 순회하면서 채워주면 되는데, 뒤에서부터 채울 수 있도록 revered를 취해 순회한다.
• 가장 중요한 점화식 관계는 pibo[i][j] = pibo[i - 1][j] + pibo[i][j + 1]가 된다.
• 이중 for문으로 pibo 리스트를 전부 채웠다면 pibo[n][0]이 구하는 답이 된다.

4. 파이썬 코드

from math import pi

n = int(input())
pibo = [[0] * (int(i / pi) + 1) for i in range(n + 1)]
pibo[0][-1] = 1
for i in range(n + 1):
    pibo[i][-1] = 1
    for j in reversed(range(len(pibo[i]) - 1)):
        pibo[i][j] = (pibo[i - 1][j] + pibo[i][j + 1]) % 10**18
print(pibo[n][0])