[백준1003번][백준][baekjoon][1003번][DynamicProgramming][DP][피보나치함수][Python][파이썬]

문제링크

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

1003번: 피보나치 함수

문제

 

풀이

문제를 보자마자 딱 DP로 풀어야 할 것 같은 감이 드는 문제입니다. 반복 또는 재귀로 피보나치 함수를 구현하는 문제는 많이들 해보셨을 것 같습니다. 이 문제는 그중에서도 피보나치 함수의 재귀 호출 횟수를 계산하는 문제입니다. 피보나치 함수의 재귀 호출 자체가 DP가 되겠네요. 먼저 아래에 문제의 경우의 수를 표현해 보겠습니다. 인자가 0인 경우와 1인 경우는 미리 갖고 있는 것으로 가정하며, 맨 오른쪽 항에 있는 리스트 안에 숫자는 각각 Fibonacci(0)을 호출하는 횟수와 Fibonacci(1)을호출하는 횟수입니다.

 

Fibonacci(0) = [1, 0]

Fibonacci(1) = [0, 1]

Fibonacci(2) = Fibonacci(1) + Fibonacci(0) = [1, 1]

Fibonacci(3) = Fibonacci(2) + Fibonacci(1) = Fibonacci(1) + Fibonacci(0) + Fibonacci(1) = [2,1]

Fibonacci(4) = Fibonacci(3) + Fibonacci(2) = Fibonacci(2) + Fibonacci(1) + Fibonacci(2)

                = Fibonacci(1) + Fibonacci(0) +Fibonacci(1) + Fibonacci(1) + Fibonacci(0) = [3,2]

 

 

이 문제의 경우의 수를 나타내보니 한눈에 쉽게 보이는 것을 알 수 있습니다. 점화식을 세우면 아래와 같습니다.

 

D[N] = D[N-1] + D[N-2]

 

2차원 배열을 사용하거나 튜플, 딕셔너리 등을 사용해도 괜찮을 것 같지만, 저는 그냥 Fibonacci(0) 호출 Fibonacci(1) 호출 횟수를 저장하는 리스트를 두 개 만들었습니다.

코드

#python

testcase=int(input())
 
dp0=[ 0 for _ in range(41)]
dp1=[ 0 for _ in range(41)]
 
dp0[0]=1
dp1[1]=1
 
for i in range(2,41):
    dp0[i]=dp0[i-1]+dp0[i-2]
    dp1[i]=dp1[i-1]+dp1[i-2]
 
for i in range(testcase):
    a=int(input())
    print("%d %d"%(dp0[a],dp1[a]))

 

오류 또는 더 좋은 풀이 방법이 있다면 댓글로 남겨주세요.

이번 포스팅에서는 python으로 작성하였지만, 추후 C와 C++ 코드도 올리도록 하겠습니다.