백준 24416. 알고리즘 수업 - 피보나치 수 1

http://acmicpc.net/problem/24416

24416번: 알고리즘 수업 - 피보나치 수 1

동적 프로그래밍 문제. 처음 접해봤는데, 재귀보다 호출 횟수가 현저히 적어서 신선했다.

문제는 간단해서 주어진 수도 코드를 구현하면 된다.

 

n = int(input())

count_1 = 0
count_2 = 0

def fib_r(n):
	global count_1
	if n == 1 or n == 2:
		count_1 += 1
		return 1
	return fib_r(n-1) + fib_r(n-2)

def fib():
	global count_2
	count = 0
	f = [1]* n
	for i in range(2, n):
		f[i] = f[i - 1] + f[i - 2]
		count_2 += 1

fib_r(n)
fib()

print(count_1, count_2)