백준 1003 피보나치 함수 - python

1003번: 피보나치 함수 (acmicpc.net)

1003번: 피보나치 함수

 

문제 )

 fibonacci(n)이 n번째 피보나치 수를 의미할 때 fibonacci(n)이 호출되면 0, 1이 몇번 출력되는가?

 

풀이 )

이 문제는 dp 로 푸는 문제이다. 

0 을 호출한 횟수, 1을 호출한 횟수를 리스트에 메모이제이션으로 담는다.

•  메모이제이션은 이전에 계산된 결과를 일시적으로 기록해 놓는 넓은 개념을 의미한다.

           0                     1

f(0)       1                     0

f(1)       0                     1

f(2)       1                     1

f(3)       1                     2

f(4)       2                     3

f(5)       3                     5

 

f(0) 부터 f(5) 까지 0과 1이 몇 번 호출되는지 세어 보니, 이것 역시 점화식으로 표현할 수 있음을 알 수 있다. 

따라서 리스트로 나타내면 

zero = [ 1, 0 ,1, 1, 2, 3, ,,,, ]

one = [0, 1, 1, 2, 3, 5, ,,,, ]

이렇게 다 리스트에 담아둔 다음에

받아온 숫자의 인덱스를 리스트에서 찾아가면 몇 번의 0과 1이 호출되는지 알 수 있다. 

 

즉, 이문제는 bottom-up 방식으로 작은 문제부터 해결하여 큰 문제를 해결하는 방식으로 풀 수 있었따. 

여기서 결과 저장용 리스트를 DP 테이블이라고도 한다.