[백준] 1003번 피보나치 함수

fibonacci (이하 F) 는 F(0)일땐 0이 1 번 호출 , F(1)일땐 1이 한번 호출 된다고 했다..

그럼 F(2)는? 피보나치는 F(n-2) + F(n-1) 의 점화식을 가지고 있으니 0이 1번 호출, 1이 한번 호출 될 것이다.

그럼 이것을 소스로 풀이해보면...

사실 배열을 통해서 만들어도 되는데, 누구한테 보여줄 소스도 아니고 내가 보고 편하게 하기 위해서 vector<pair>>를 사용했다.

사실 최대 입력하는 갯수가 40개 이하라고 했으니, reserve 로 40까지 잡아줬어야했는데 내 불찰인것 같다. 나중에 수정하자.

벡터가 첨자연산([])을 지원하니, vt[0] 일땐, F(0)과 같다고 보면 된다.

 즉 vt[0].first = 1, vt[0].second = 0 ( first는 return 0이 몇번 호출됐는가, second는 return 1이 몇번 호출됐는가로 판단 )

그렇다면 vt[1]은 F(1)과 같을테니 vt[1].first = 0, vt[1].second = 1이 된다.

vt[2] 부터는 vt[0] + vt[1] 이 될 것이다. (점화식이 F(n-2) + F(n-1) 이므로) 그러므로 vt[2]는 first = 1, second = 1

그럼 vt[3]은 vt[1] + vt[2] 일 것이고, vt[2]는 위에서 구했던 것처럼 first = 1, second = 1 vt[1]은 first = 0, second = 1

vt[3] : first = 1, second = 2 

이렇게 구해지는것이다.

그렇게 vt[40]번째까지 만들어두면 되겠지,

원래 문제 자체에서 Fibonacci 의 설명을 다 적어놨길래 그대로 구현하라는건가? 하고 보니

최대 실행시간이 0.25초 였다. 

일반 재귀로는 풀수없다고 판단돼서 동적계획법을 사용함..

배열로 풀걸 왜 벡터로 풀었을까는 그냥 내가 벡터를 쓰고 싶어서 였다.