다이나믹 프로그래밍 정복 -피보나치 변형 몇가지-

1. 문제

 

17175번: 피보나치는 지겨웡~ (acmicpc.net)

17175번: 피보나치는 지겨웡~

 

피보나치 함수의 호출 횟수를 구하는 문제

 

 

2. 풀이

 

재귀 함수의 호출 횟수를 곧이 곧대로 구하면 풀 수 없다

 

def fibonacci(n):
    
    global cnt

    cnt += 1

    if n < 2:
        
        return n
    
    return fibonacci(n-2)+fibonacci(n-1)

 

중간에 cnt를 넣어가지고 cnt를 구하면 함수의 호출횟수가 되는데 n이 조금만 커져도 도저히 시간안에 함수가 끝나질 않아서 cnt를 구하질 못해

 

그래서 n에 따라 호출 횟수를 한번 구해보니까 이것마저도 하나의 수열을 이루더라

 

1, 1, 3, 5, 9, 15, 25, 41, 67, 109, 177, ...

 

이 수열의 계차수열이 0,2,2,4,6,10,16,...으로 피보나치 수열을 이룬다

 

계차수열은 어떻게 처리하냐?? 공식을 써야하냐?

 

아니다 그냥 하나의 minus_dp를 더 만들어서 원래 dp에 더해나가면 된다

 

계차수열 b[n-1] = a[n]-a[n-1]이므로...

 

a[n] = a[n-1] + b[n-1]을 이용해서 

 

b[n-1]을 먼저 구하고.. a[n-1]에 더해나가자

 

from sys import stdin

n = int(stdin.readline())

div = 1000000007

if n <= 1:
    
    print(1)

elif n == 2:
    
    print(3)

elif n == 3:
    
    print(5)

else:
    dp = [0]*(n+1)

    dp[0] = 1
    dp[1] = 1
    dp[2] = 3
    dp[3] = 5

    minus_dp = [0]*(n)

    minus_dp[0] = 1
    minus_dp[1] = 2
    minus_dp[2] = 2

    for i in range(3,n):
        
        minus_dp[i] = (minus_dp[i-1]+minus_dp[i-2])%div

        dp[i+1] = (dp[i]+minus_dp[i])%div

    print(dp[n])

 

위와 같이 minus_dp가 하나의 피보나치 수열을 이루므로 minus_dp를 피보나치로 먼저 구하고..

 

dp[i+1] - dp[i] = minus_dp[i] 니까... 이러한 사실을 이용해서 dp[i], minus_dp[i]로부터 dp[i+1]을 구한다

 

더하는 과정에서 div로 계속 나눠주면서 저장해나가면 시간을 줄일수 있다는건 이제 지겨운 사실

 

 

3. 문제2

 

1788번: 피보나치 수의 확장 (acmicpc.net)

1788번: 피보나치 수의 확장

 

음수에서도 피보나치 수열을 정의할때, 피보나치 수를 구해본다면?

 

4. 풀이2

 

어려운거 없이 조금만 써보면 규칙을 알 수 있다

 

양수에 대해서는 그냥 더해나가면 되는데 결국엔 n이 음수가 문제다

 

f(1) = f(0) + f(-1)이므로, f(-1) = 1

 

f(0) = f(-1) + f(-2)이므로, f(-2) = -1

 

f(-1) = f(-2) + f(-3)이므로 f(-3) = 2

 

f(-2) = f(-3) + f(-4)이므로.. f(-4) = -3

 

f(-3) = f(-4) + f(-5)이므로 f(-5) = 5

 

...

 

그러면 -n일때 피보나치의 값은.. n이 홀수이면 양수이고 n이 짝수이면 음수가 붙으며 절댓값은 1,1,2,3,5,...로 피보나치 수열을 이룬다

 

양수에도 0,1,1,2,3,5,.. 똑같이 피보나치 수열을 이루고 있으므로..

 

결국에 dp[n]은 0,1,1,2,3,5,..로 시작하는 피보나치 수열을 1,000,000,000으로 나눈 값을 저장해나가면 될 것이고

 

n이 음수일때는 만약에 n의 절댓값이 홀수이면 양수이고 n의 절댓값이 짝수이면 음수이므로, 이것을 이용하면 된다

 

from sys import stdin

n = int(stdin.readline())

if n == 0:
    
    print(0)
    print(0)

elif n == 1:
    
    print(1)
    print(1)

elif n == -1:
    
    print(1)
    print(1)

else:
    
    dp = [0]*(abs(n)+1)
    dp[1] = 1

    for i in range(2,abs(n)+1):
        
        dp[i] = (dp[i-1]+dp[i-2])%1000000000
    
    if n > 1:

        print(1)
        print(dp[n])
    
    elif n < -1:
        
        if abs(n) % 2 == 0:
            
            print(-1)
            print(dp[abs(n)])
        
        else:
            
            print(1)
            print(dp[abs(n)])