[백준 1003] 피보나치 함수 풀이노트

1차 풀이 (2018-07-05, 1988 KB, 4 MS)

F(n) = F(n-1) + F(n-2) 이므로,  N(n, x) = N(n-1, x) + N(n-2, x) 일 것 이다. 

* N(n, x) : F(n)을 호출했을 때, F(x)를 호출한 횟수를 반환.

* 표로 만들어보면 N(n, 0) = F(n-2) 이고, N(n, 1) = F(n-1) 임을 알 수 있다. 

F(n)의 결과를 캐싱해둔다면 시간을 효과적으로 단축할 수 있다. 

* F(n)의 결과가 있다면 F(n-2)를 굳이 처음부터 다시 계산할 필요가 없다.