시간 제한 메모리 제한 제출 정답 맞은 사람 정답 비율
1 초 128 MB 52852 20356 16975 38.640%

문제

피보나치 수는 0과 1로 시작한다. 0번째 피보나치 수는 0이고, 1번째 피보나치 수는 1이다. 그 다음 2번째 부터는 바로 앞 두 피보나치 수의 합이 된다.

이를 식으로 써보면 Fn = Fn-1 + Fn-2 (n ≥ 2)가 된다.

n=17일때 까지 피보나치 수를 써보면 다음과 같다.

0, 1, 1, 2, 3, 5, 8, 13, 21, 34, 55, 89, 144, 233, 377, 610, 987, 1597

n이 주어졌을 때, n번째 피보나치 수를 구하는 프로그램을 작성하시오.

입력

첫째 줄에 n이 주어진다. n은 90보다 작거나 같은 자연수이다.

출력

첫째 줄에 n번째 피보나치 수를 출력한다.

예제 입력 1

10

예제 출력 1

55
W3sicHJvYmxlbV9pZCI6IjI3NDgiLCJwcm9ibGVtX2xhbmciOiIwIiwidGl0bGUiOiJcdWQ1M2NcdWJjZjRcdWIwOThcdWNlNTggXHVjMjE4IDIiLCJkZXNjcmlwdGlvbiI6IjxwPlx1ZDUzY1x1YmNmNFx1YjA5OFx1Y2U1OCBcdWMyMThcdWIyOTQgMFx1YWNmYyAxXHViODVjIFx1YzJkY1x1Yzc5MVx1ZDU1Y1x1YjJlNC4gMFx1YmM4OFx1YzlmOCBcdWQ1M2NcdWJjZjRcdWIwOThcdWNlNTggXHVjMjE4XHViMjk0IDBcdWM3NzRcdWFjZTAsIDFcdWJjODhcdWM5ZjggXHVkNTNjXHViY2Y0XHViMDk4XHVjZTU4IFx1YzIxOFx1YjI5NCAxXHVjNzc0XHViMmU0LiBcdWFkZjggXHViMmU0XHVjNzRjIDJcdWJjODhcdWM5ZjggXHViZDgwXHVkMTMwXHViMjk0IFx1YmMxNFx1Yjg1YyBcdWM1NWUgXHViNDUwIFx1ZDUzY1x1YmNmNFx1YjA5OFx1Y2U1OCBcdWMyMThcdWM3NTggXHVkNTY5XHVjNzc0IFx1YjQxY1x1YjJlNC48XC9wPlxyXG5cclxuPHA+XHVjNzc0XHViOTdjIFx1YzJkZFx1YzczY1x1Yjg1YyBcdWMzNjhcdWJjZjRcdWJhNzQgRjxzdWI+bjxcL3N1Yj4gPSBGPHN1Yj5uLTE8XC9zdWI+ICsgRjxzdWI+bi0yPFwvc3ViPiAobiAmZ2U7IDIpXHVhYzAwIFx1YjQxY1x1YjJlNC48XC9wPlxyXG5cclxuPHA+bj0xN1x1Yzc3Y1x1YjU0YyBcdWFlNGNcdWM5YzAgXHVkNTNjXHViY2Y0XHViMDk4XHVjZTU4IFx1YzIxOFx1Yjk3YyBcdWMzNjhcdWJjZjRcdWJhNzQgXHViMmU0XHVjNzRjXHVhY2ZjIFx1YWMxOVx1YjJlNC48XC9wPlxyXG5cclxuPHA+MCwgMSwgMSwgMiwgMywgNSwgOCwgMTMsIDIxLCAzNCwgNTUsIDg5LCAxNDQsIDIzMywgMzc3LCA2MTAsIDk4NywgMTU5NzxcL3A+XHJcblxyXG48cD5uXHVjNzc0IFx1YzhmY1x1YzViNFx1Yzg0Y1x1Yzc0NCBcdWI1NGMsIG5cdWJjODhcdWM5ZjggXHVkNTNjXHViY2Y0XHViMDk4XHVjZTU4IFx1YzIxOFx1Yjk3YyBcdWFkNmNcdWQ1NThcdWIyOTQgXHVkNTA0XHViODVjXHVhZGY4XHViN2E4XHVjNzQ0IFx1Yzc5MVx1YzEzMVx1ZDU1OFx1YzJkY1x1YzYyNC48XC9wPlxyXG4iLCJpbnB1dCI6IjxwPlx1Y2NhYlx1YzlmOCBcdWM5MDRcdWM1ZDAgblx1Yzc3NCBcdWM4ZmNcdWM1YjRcdWM5YzRcdWIyZTQuIG5cdWM3NDAgOTBcdWJjZjRcdWIyZTQgXHVjNzkxXHVhYzcwXHViMDk4IFx1YWMxOVx1Yzc0MCBcdWM3OTBcdWM1ZjBcdWMyMThcdWM3NzRcdWIyZTQuPFwvcD5cclxuIiwib3V0cHV0IjoiPHA+XHVjY2FiXHVjOWY4IFx1YzkwNFx1YzVkMCBuXHViYzg4XHVjOWY4IFx1ZDUzY1x1YmNmNFx1YjA5OFx1Y2U1OCBcdWMyMThcdWI5N2MgXHVjZDljXHViODI1XHVkNTVjXHViMmU0LjxcL3A+XHJcbiIsImhpbnQiOiIiLCJvcmlnaW5hbCI6IjEiLCJodG1sX3RpdGxlIjoiMCIsInByb2JsZW1fbGFuZ190Y29kZSI6IktvcmVhbiJ9LHsicHJvYmxlbV9pZCI6IjI3NDgiLCJwcm9ibGVtX2xhbmciOiIxIiwidGl0bGUiOiJGaWJvbmFjY2kgTnVtYmVyIDIiLCJkZXNjcmlwdGlvbiI6IjxwPlRoZSBGaWJvbmFjY2kgc2VxdWVuY2UgaXMgY2FsY3VsYXRlZCBieSBhZGRpbmcgdGhlIHByZXZpb3VzIHR3byBudW1iZXJzIG9mIHRoZSBzZXF1ZW5jZS4gVGhlIGZpcnN0IHR3byBudW1iZXJzIGluIHRoZSBGaWJvbmFjY2kgbnVtYmVyIGFyZSAwIGFuZCAxLjxcL3A+XHJcblxyXG48cD5UaGUgc2VxdWVuY2UmbmJzcDtGbiBvZiBGaWJvbmFjY2kgbnVtYmVycyBpcyBkZWZpbmVkIGJ5IHRoZSByZWN1cnJlbmNlIHJlbGF0aW9uOiBGPHN1Yj5uPFwvc3ViPiA9IEY8c3ViPm4tMTxcL3N1Yj4gKyBGPHN1Yj5uLTI8XC9zdWI+IChuICZnZTsgMikuPFwvcD5cclxuXHJcbjxwPkdpdmVuIGFuIGludGVnZXIgbiwgd3JpdGUgYSBwcm9ncmFtIHdoaWNoIHByaW50cyBudGggRmlib25hY2NpIG51bWJlci48XC9wPlxyXG4iLCJpbnB1dCI6IjxwPlRoZSBmaXJzdCBsaW5lIGNvbnRhaW5zJm5ic3A7b25lIGludGVnZXImbmJzcDtuLiAoMSAmbGU7IG4gJmxlOyA5MCk8XC9wPlxyXG4iLCJvdXRwdXQiOiI8cD5PdXRwdXQgb25lIGxpbmUgb2Ygb25lIGludGVnZXIsIG50aCBGaWJvbmFjY2kgbnVtYmVyLjxcL3A+XHJcbiIsImhpbnQiOiIiLCJvcmlnaW5hbCI6IjAiLCJodG1sX3RpdGxlIjoiMCIsInByb2JsZW1fbGFuZ190Y29kZSI6IkVuZ2xpc2gifV0=