Informatica Online Judge

  피보나치 수열 (Advance) [0155 / 009B]

Time Limit(Test case) : 1000(ms)
Number of users who solved : 1237   Total Tried : 1549


The Champion of this Problem (C++) : gs19074 - ms / 168byte
My Best Submission (C++) : N/A

[]

Background

피보나치 수는 다음과 같이 정의된다.


$f_1 = 1, f_2 = 1$
$f_n = f_{n-1} + f_{n-2} (n > 2)$

한 정수를 입력받아서 $f_n$을 구하는 프로그램을 작성하시오.

단, 재귀함수로 작성하시오.
일반 재귀함수로는 시간초과가 발생된다.

Input

첫째 줄에 한 정수 $n$이 입력된다.

[입력값의 정의역]

$1 \leq n \leq 90$

Output

$n$번째 피보나치 수를 출력한다.

IO Example

입력
3

출력
2

Submit : [C/C++] | [C++11] | [Obj-C] | [Java] | [Python]
Prob Analysis : [Problem Statistics] | [Solution]