문제
피보나치 수열은 다음과 같이 그 전 두 항의 합으로 계산되는 수열이다. 첫 두 항은 1로 정의된다.
f(1) = 1, f(2) = 1, f(n > 2) = f(n − 1) + f(n − 2)
정수를 입력받아, 그에 해당하는 피보나치 수를 출력하는 프로그램을 작성하여라.
예제 출력 1
354224848179261915075
힌트
해당 테스트 데이터의 모든 정답은 1000자를 넘지 않는다. ( f(20) = 6765 이므로 4자다. )
W3sicHJvYmxlbV9pZCI6IjQxNTAiLCJwcm9ibGVtX2xhbmciOiIwIiwidGl0bGUiOiJcdWQ1M2NcdWJjZjRcdWIwOThcdWNlNTggXHVjMjE4IiwiZGVzY3JpcHRpb24iOiI8cD5cdWQ1M2NcdWJjZjRcdWIwOThcdWNlNTggXHVjMjE4XHVjNWY0XHVjNzQwIFx1YjJlNFx1Yzc0Y1x1YWNmYyBcdWFjMTlcdWM3NzQmbmJzcDtcdWFkZjggXHVjODA0IFx1YjQ1MCBcdWQ1NmRcdWM3NTggXHVkNTY5XHVjNzNjXHViODVjIFx1YWNjNFx1YzBiMFx1YjQxOFx1YjI5NCBcdWMyMThcdWM1ZjRcdWM3NzRcdWIyZTQuIFx1Y2NhYiBcdWI0NTAgXHVkNTZkXHVjNzQwIDFcdWI4NWMgXHVjODE1XHVjNzU4XHViNDFjXHViMmU0LjxcL3A+XHJcblxyXG48cCBzdHlsZT1cInRleHQtYWxpZ246IGNlbnRlcjtcIj5mKDEpID0gMSwgZigyKSA9IDEsIGYobiAmZ3Q7IDIpID0gZihuICZtaW51czsgMSkgKyBmKG4gJm1pbnVzOyAyKTxcL3A+XHJcblxyXG48cD5cdWM4MTVcdWMyMThcdWI5N2MgXHVjNzg1XHViODI1XHViYzFiXHVjNTQ0LCBcdWFkZjhcdWM1ZDAgXHVkNTc0XHViMmY5XHVkNTU4XHViMjk0IFx1ZDUzY1x1YmNmNFx1YjA5OFx1Y2U1OCBcdWMyMThcdWI5N2MgXHVjZDljXHViODI1XHVkNTU4XHViMjk0IFx1ZDUwNFx1Yjg1Y1x1YWRmOFx1YjdhOFx1Yzc0NCBcdWM3OTFcdWMxMzFcdWQ1NThcdWM1ZWNcdWI3N2MuPFwvcD5cclxuIiwiaW5wdXQiOiIiLCJvdXRwdXQiOiIiLCJoaW50IjoiPHA+XHVkNTc0XHViMmY5IFx1ZDE0Y1x1YzJhNFx1ZDJiOCBcdWIzNzBcdWM3NzRcdWQxMzBcdWM3NTggXHViYWE4XHViNGUwIFx1YzgxNVx1YjJmNVx1Yzc0MCAxMDAwXHVjNzkwXHViOTdjIFx1YjExOFx1YzljMCBcdWM1NGFcdWIyOTRcdWIyZTQuICggZigyMCkgPSA2NzY1IFx1Yzc3NFx1YmJjMFx1Yjg1YyA0XHVjNzkwXHViMmU0LiZuYnNwOyk8XC9wPlxyXG4iLCJvcmlnaW5hbCI6IjAiLCJodG1sX3RpdGxlIjoiMCIsInByb2JsZW1fbGFuZ190Y29kZSI6IktvcmVhbiJ9LHsicHJvYmxlbV9pZCI6IjQxNTAiLCJwcm9ibGVtX2xhbmciOiIxIiwidGl0bGUiOiJGaWJvbmFjY2kgTnVtYmVycyIsImRlc2NyaXB0aW9uIjoiPHA+QSBGaWJvbmFjY2kgc2VxdWVuY2UgaXMgY2FsY3VsYXRlZCBieSBhZGRpbmcgdGhlIHByZXZpb3VzIHR3byBtZW1iZXJzIG9mIHRoZSBzZXF1ZW5jZSwgd2l0aCB0aGUgZmlyc3QgdHdvIG1lbWJlcnMgYmVpbmcgYm90aCAxLjxcL3A+XHJcblxyXG48cCBzdHlsZT1cInRleHQtYWxpZ246IGNlbnRlcjtcIj5mKDEpID0gMSwgZigyKSA9IDEsIGYobiAmZ3Q7IDIpID0gZihuICZtaW51czsgMSkgKyBmKG4gJm1pbnVzOyAyKTxcL3A+XHJcblxyXG48cD5Zb3VyIHRhc2sgaXMgdG8gdGFrZSBhIG51bWJlciBhcyBpbnB1dCwgYW5kIHByaW50IHRoYXQgZmlib25hY2NpIG51bWJlci48XC9wPlxyXG4iLCJpbnB1dCI6IiIsIm91dHB1dCI6IiIsImhpbnQiOiI8cD5ObyBnZW5lcmF0ZWQgZmlib25hY2NpIG51bWJlciBpbiBleGNlc3Mgb2YgMTAwMCBkaWdpdHMgd2lsbCBiZSBpbiB0aGUgdGVzdCBkYXRhLCBpLmUuIGYoMjApID0gNjc2NSBoYXMgNCBkaWdpdHMuPFwvcD5cclxuIiwib3JpZ2luYWwiOiIxIiwiaHRtbF90aXRsZSI6IjAiLCJwcm9ibGVtX2xhbmdfdGNvZGUiOiJFbmdsaXNoIn1d