DP는 점화식을 찾는게 힘들어... 근데 분할정복임 (#11444)

#11444 피보나치 수 6 https://www.acmicpc.net/problem/11444

 

제일 처음 접근했던 방식은, DP를 재귀로 돌리는 형태였다.

 

import sys

sys.setrecursionlimit(10000)

n = int(input())
division = 1000000007
dp = [0, 1]


def find_fibo(n):
    # print(n)
    if n < len(dp):
        # print(n, "len", len(dp))
        return dp[n]
    else:
        a = find_fibo(n - 2)
        b = find_fibo(n - 1)
        # print(a, b)
        result = (a + b) % division
        dp.append(result)
        return result


print(find_fibo(n))
# print(dp)

하지만 재귀의 깊이가 너무 깊어졌다.

 

거의 반 포기상태로 참고자료를 봤고,

점화식을 훨씬 더 함축적으로 개선해야함을 느꼈다.

 

 

최종적으로 파악한 점화식은 다음과 같다.

*출처

https://velog.io/@kjy2134/%EB%B0%B1%EC%A4%80-11444-%ED%94%BC%EB%B3%B4%EB%82%98%EC%B9%98-%EC%88%98-%ED%8C%8C%EC%9D%B4%EC%8D%AC

백준 11444 피보나치 수 : 파이썬

점화식을 검증하기 위해 손으로 계산을 해봤다.

우측 상단을 보면, 처음에 계산을 하는 과정에서 점화식을 접근하는 모습이 보인다.

이 때 약간 쎄한 느낌이 들었었는데, 그 느낌을 무시하지 말았어야 했다....

 

 

문제의 핵심은,

입력의 크기가 너무 크기 때문에 절반으로 나눠서 계산하는 것이다.

분할-정복 기법을 쓸 때는, 입력을 반으로 나누는 방식을 먼저 생각할 필요가 있는 것 같다.

 

 

 

그렇게 코드를 수정할 수 있었다.

import sys

sys.setrecursionlimit(10000000)

n = int(input())
division = 1000000007
dp = dict()
# print(dp)
dp[0], dp[1], dp[2] = 0, 1, 1


def find_fibo(n):
    # print(dp)
    # print(n)
    if n <= 2:
        return dp[n]
    try:
        # print(n, "len", len(dp))
        return dp[n]
    except:
        half = n // 2
        if n % 2:  # == 1
            h0 = find_fibo(half + 1)
            h1 = find_fibo(half)
            # print(a, b)
            dp[n] = (h0**2 + h1**2) % division
            return dp[n]
        else:  # n%2 == 0
            h0 = find_fibo(half)
            h1 = find_fibo(half - 1)
            dp[n] = ((h1 * 2 + h0) * h0) % division
            # print(dp)
            return dp[n]


print(find_fibo(n))
# print(dp)