시간 제한 메모리 제한 제출 정답 맞은 사람 정답 비율
1 초 128 MB 11317 4527 4023 42.334%

문제

피보나치 수는 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

힌트

W3sicHJvYmxlbV9pZCI6IjI3NDgiLCJwcm9ibGVtX2xhbmciOiIwIiwidGl0bGUiOiJcdWQ1M2NcdWJjZjRcdWIwOThcdWNlNTggXHVjMjE4IDIiLCJkZXNjcmlwdGlvbiI6IjxwPlxyXG5cdFx1ZDUzY1x1YmNmNFx1YjA5OFx1Y2U1OCBcdWMyMThcdWIyOTQgMFx1YWNmYyAxXHViODVjIFx1YzJkY1x1Yzc5MVx1ZDU1Y1x1YjJlNC4gMFx1YmM4OFx1YzlmOCBcdWQ1M2NcdWJjZjRcdWIwOThcdWNlNTggXHVjMjE4XHViMjk0IDBcdWM3NzRcdWFjZTAsIDFcdWJjODhcdWM5ZjggXHVkNTNjXHViY2Y0XHViMDk4XHVjZTU4IFx1YzIxOFx1YjI5NCAxXHVjNzc0XHViMmU0LiBcdWFkZjggXHViMmU0XHVjNzRjIDJcdWJjODhcdWM5ZjggXHViZDgwXHVkMTMwXHViMjk0IFx1YmMxNFx1Yjg1YyBcdWM1NWUgXHViNDUwIFx1ZDUzY1x1YmNmNFx1YjA5OFx1Y2U1OCBcdWMyMThcdWM3NTggXHVkNTY5XHVjNzc0IFx1YjQxY1x1YjJlNC48XC9wPlxyXG48cD5cclxuXHRcdWM3NzRcdWI5N2MgXHVjMmRkXHVjNzNjXHViODVjIFx1YzM2OFx1YmNmNFx1YmE3NCBGPHN1Yj5uPFwvc3ViPiA9IEY8c3ViPm4tMTxcL3N1Yj4gKyBGPHN1Yj5uLTI8XC9zdWI+IChuJmd0Oz0yKVx1YWMwMCBcdWI0MWNcdWIyZTQuPFwvcD5cclxuPHA+XHJcblx0bj0xN1x1Yzc3Y1x1YjU0YyBcdWFlNGNcdWM5YzAgXHVkNTNjXHViY2Y0XHViMDk4XHVjZTU4IFx1YzIxOFx1Yjk3YyBcdWMzNjhcdWJjZjRcdWJhNzQgXHViMmU0XHVjNzRjXHVhY2ZjIFx1YWMxOVx1YjJlNC48XC9wPlxyXG48cD5cclxuXHQwLCAxLCAxLCAyLCAzLCA1LCA4LCAxMywgMjEsIDM0LCA1NSwgODksIDE0NCwgMjMzLCAzNzcsIDYxMCwgOTg3LCAxNTk3PFwvcD5cclxuPHA+XHJcblx0blx1Yzc3NCBcdWM4ZmNcdWM1YjRcdWM4NGNcdWM3NDQgXHViNTRjLCBuXHViYzg4XHVjOWY4IFx1ZDUzY1x1YmNmNFx1YjA5OFx1Y2U1OCBcdWMyMThcdWI5N2MgXHVhZDZjXHVkNTU4XHViMjk0IFx1ZDUwNFx1Yjg1Y1x1YWRmOFx1YjdhOFx1Yzc0NCBcdWM3OTFcdWMxMzFcdWQ1NThcdWMyZGNcdWM2MjQuPFwvcD5cclxuIiwiaW5wdXQiOiI8cD5cclxuXHRcdWNjYWJcdWM5ZjggXHVjOTA0XHVjNWQwIG5cdWM3NzQgXHVjOGZjXHVjNWI0XHVjOWM0XHViMmU0LiBuXHVjNzQwIDkwXHViY2Y0XHViMmU0IFx1Yzc5MVx1YWM3MFx1YjA5OCBcdWFjMTlcdWM3NDAgXHVjNzkwXHVjNWYwXHVjMjE4XHVjNzc0XHViMmU0LjxcL3A+XHJcbiIsIm91dHB1dCI6IjxwPlxyXG5cdFx1Y2NhYlx1YzlmOCBcdWM5MDRcdWM1ZDAgblx1YmM4OFx1YzlmOCBcdWQ1M2NcdWJjZjRcdWIwOThcdWNlNTggXHVjMjE4XHViOTdjIFx1Y2Q5Y1x1YjgyNVx1ZDU1Y1x1YjJlNC48XC9wPlxyXG4iLCJoaW50IjoiIiwib3JpZ2luYWwiOiIxIiwicHJvYmxlbV9sYW5nX2NvZGUiOiJcdWQ1NWNcdWFkNmRcdWM1YjQifSx7InByb2JsZW1faWQiOiIyNzQ4IiwicHJvYmxlbV9sYW5nIjoiMSIsInRpdGxlIjoiRmlib25hY2NpIE51bWJlciAyIiwiZGVzY3JpcHRpb24iOiI8cD5UaGUgRmlib25hY2NpIHNlcXVlbmNlIGlzIGNhbGN1bGF0ZWQgYnkgYWRkaW5nIHRoZSBwcmV2aW91cyB0d28gbnVtYmVycyBvZiB0aGUgc2VxdWVuY2UuIFRoZSBmaXJzdCB0d28gbnVtYmVycyBpbiB0aGUgRmlib25hY2NpIG51bWJlciBhcmUgMCBhbmQgMS48XC9wPlxyXG5cclxuPHA+VGhlIHNlcXVlbmNlJm5ic3A7Rm4gb2YgRmlib25hY2NpIG51bWJlcnMgaXMgZGVmaW5lZCBieSB0aGUgcmVjdXJyZW5jZSByZWxhdGlvbjogRjxzdWI+bjxcL3N1Yj4gPSBGPHN1Yj5uLTE8XC9zdWI+ICsgRjxzdWI+bi0yPFwvc3ViPiAobiAmZ2U7IDIpLjxcL3A+XHJcblxyXG48cD5HaXZlbiBhbiBpbnRlZ2VyIG4sIHdyaXRlIGEgcHJvZ3JhbSB3aGljaCBwcmludHMgbnRoIEZpYm9uYWNjaSBudW1iZXIuPFwvcD5cclxuIiwiaW5wdXQiOiI8cD5UaGUgZmlyc3QgbGluZSBjb250YWlucyZuYnNwO29uZSBpbnRlZ2VyJm5ic3A7bi4gKDEgJmxlOyBuICZsZTsgOTApPFwvcD5cclxuIiwib3V0cHV0IjoiPHA+T3V0cHV0IG9uZSBsaW5lIG9mIG9uZSBpbnRlZ2VyLCBudGggRmlib25hY2NpIG51bWJlci48XC9wPlxyXG4iLCJoaW50IjoiIiwib3JpZ2luYWwiOiIwIiwicHJvYmxlbV9sYW5nX2NvZGUiOiJcdWM2MDFcdWM1YjQifV0=