[Python] 1737번 Pibonacci

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

1737번: Pibonacci

---

 

22/11/08

 

 

신박한 2차원 DP문제로, 처음에는 재귀를 이용한 탑다운 방식으로 접근했었으나, 재귀 시간이 너무 오래 걸려 바텀업 방식으로 전환하여 풀 수 있었던 문제다.

---

 

문제 접근 방식:

 

 

이 문제를 보면, 기존 피보나치수열의 점화식과는 다르게 아래와 같은 점화식을 가지고 있다.

 

 

맨 처음 생각한 풀이는 위의 점화식을 재귀로 구현하고, DP테이블은 딕셔너리로 구현함으로써 하려고 했다.

 

딕셔너리의 키는 실수 연산을 통해서 구현하려고 했다.

 

근데, 이렇게 하니 재귀 자체의 시간이 오래 걸렸다.

 

그렇다고 재귀(탑다운)가 아닌 for문을 이용한 바텀업 방식으로 구현하려고 하자니, DP테이블을 채우기가 참 애매했었다.

 

 

그래서 두 번째로 생각한 풀이는, 다음과 같았다.

 

먼저 n*n크기의 2차원 DP테이블을 하나 만들어 준다.

 

어떤 n이 주어져 있을 때 DP식은 아래와 같다.

 

 

왜 이런 DP식을 떠올렸냐고 한다면, 점화식의 구성을 보면 빼는 숫자는 1과 pi밖에 없기 때문이다.

 

때문에 n에서 1을 몇 번 뺐냐, pi를 몇 번 뺐냐의 값을 저장한다면, 쉽게 해결할 수 있으리라고 생각했다.

 

 

처음에는 이를 재귀를 사용하여 탑 다운 방식으로 구현했었다.

 

i와 j를 이용해 현재 숫자(n - i - j*pi)를 계산했다.

 

만약 이 숫자가 만약 0과 pi사이에 있으면 dp[i][j]를 1로 저장하고 이를 반환,

만약 0보다 작으면 dp[i][j]를 0으로 저장하고 0을 반환,

만약 dp[i][j]가 이미 있으면 이를 반환하고, 없으면 재귀를 사용하여 dp[i+1][j]와 dp[i][j+1]을 구해서 두 개를 더해서 구했다.

 

이렇게 했더니 재귀 깊이가 너무 많이 들어가서 시간이 오래 걸렸다.

 

그래서 이를 for문을 사용해서 구현했더니 맞았습니다를 받을 수 있었다.

 

 

만약, 시간이 충분하다면 1부터 1000까지이므로, 데이터를 미리 계산을 해서 그냥 답만 나오게 할 수도 있다.

---

아래는 내가 위의 접근 방식과 같이 작성한 파이썬 코드이다. 더보기를 누르면 확인할 수 있다.

# 1737번 Pibonacci
# 2차원 DP
from math import pi
MOD = 1000000000000000000
# dp[i][j] = p(n-i-j*pi)
n = int(input())
dp = [[0 for _ in range(n+1)] for _ in range(n+1)]
# 탑 다운 방식
##def pibonacci(n, i, j):
##    now_num = n - i - j*pi
##    if 0 <= now_num <= pi:
##        dp[i][j] = 1
##        return dp[i][j]
##    elif now_num < 0:
##        return 0
##    else:
##        dp[i][j] = (pibonacci(n, i+1, j) + pibonacci(n, i, j+1))%MOD
##        return dp[i][j]
# 바텀업 방식
for i in range(n-1, -1, -1):
    for j in range(n-1, -1, -1):
        now_num = n - i - j*pi
        if now_num < 0:
            dp[i][j] = 0
        elif 0 <= now_num <= pi:
            dp[i][j] = 1
        else:
            dp[i][j] = (dp[i+1][j] + dp[i][j+1]) % MOD
print(dp[0][0])