1003번: 피보나치 함수 - 동적계획법

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

1003번: 피보나치 함수

 

 

 

 

2020/07/11 - [Unity & C#] - 2748번: 피보나치 수 2 - 동적계획법

2748번과 비슷한 피보나치 문제고, 동적계획법으로 분류되어 있다.

 

아래와 같은 기본적인 피보나치 함수로 피보나치 수를 구할 때,

호출되는 Fibonacci(0)과 Fibonacci(1)의 횟수를 구해야 한다.

def Fibonacci(n):
    if n == 0:
        print ("0")
        return 0
    elif n == 1:
        print ("1")
        return 1
    else:
        return Fibonacci(n - 1) + Fibonacci(n - 2)

 

해법도 이전 문제와 다를 것 없이 메모이제이션을 이용했다.

def CountFibonacci(n):
    if len(li) < n + 1:
        li.append((li[-2][0] + li[-1][0], li[-2][1] + li[-1][1]))
        CountFibonacci(n)
    else:
        print (str(li[n][0]) + " " + str(li[n][1]))
        return



# [(1, 0), (0, 1), (1, 1), (1, 2)]

T = int(input())	# Test Case 갯수

li = [(1, 0), (0, 1)]	# 기록할 리스트

for i in range(0, T):
    N = int(input())	# 구하려는 피보나치 자리
    CountFibonacci(N)

 

리스트에 각 피보나치 자리마다 호출하는 Fibonacci(0)과 Fibonacci(1)의 횟수를 Tuple 타입으로 기록하는 방식이다.

1) li의 길이가 n + 1보다 작을 경우, len(li) + 1에 해당하는 호출 횟수 구하고 결과를 기록한다.

2) li의 길이가 n + 1일 경우, li[n]을 출력한다.

예를 들어, N번째 피보나치 수는 Fibonacci(0)을 li[N][0]회, Fibonacci(1)을 li[N][1]회 호출한다.

 

 

결과