시간 제한 메모리 제한 제출 정답 맞은 사람 정답 비율
2 초 128 MB 332 127 92 42.991%

문제

피보나치(Fibonacci) 수열은 매우 유명한 수열로 그 점화식은 F[i]=F[i-1]+F[i-2]와 같이 표현된다. 우리는 이와 같은 수열을 살짝 변경한 피보나치(Pibonacci) 수열에 대해 살펴보자. 피보나치 수열의 점화식은 아래와 같다.

P[n]  = 1 (0≤n≤π 인 경우)
 = P[n-1] + P[n-π] (그 외의 경우)

주의할 것은 n이 꼭 정수일 필요는 없다는 것이다. 즉, P[n-π] = P[n-π-1]+P[n-π-π]와 같은 식으로 계산을 해 주어야 한다.

자연수로 n이 주어졌을 때, P[n]을 구하는 프로그램을 작성하시오.

입력

첫째 줄에 자연수 n(1≤n≤1,000)이 주어진다.

출력

첫째 줄에 P[n]을 출력한다. 값이 매우 커질 수 있으므로 1,000,000,000,000,000,000으로 나눈 나머지를 출력한다.

예제 입력 1

10

예제 출력 1

19

힌트

W3sicHJvYmxlbV9pZCI6IjE3MzciLCJwcm9ibGVtX2xhbmciOiIwIiwidGl0bGUiOiJQaWJvbmFjY2kiLCJkZXNjcmlwdGlvbiI6IjxwPlx1ZDUzY1x1YmNmNFx1YjA5OFx1Y2U1OChGaWJvbmFjY2kpIFx1YzIxOFx1YzVmNFx1Yzc0MCBcdWI5ZTRcdWM2YjAgXHVjNzIwXHViYTg1XHVkNTVjIFx1YzIxOFx1YzVmNFx1Yjg1YyBcdWFkZjggXHVjODEwXHVkNjU0XHVjMmRkXHVjNzQwIEZbaV09RltpLTFdK0ZbaS0yXVx1YzY0MCBcdWFjMTlcdWM3NzQgXHVkNDVjXHVkNjA0XHViNDFjXHViMmU0LiBcdWM2YjBcdWI5YWNcdWIyOTQgXHVjNzc0XHVjNjQwIFx1YWMxOVx1Yzc0MCBcdWMyMThcdWM1ZjRcdWM3NDQgXHVjMGI0XHVjOWRkIFx1YmNjMFx1YWNiZFx1ZDU1YyBcdWQ1M2NcdWJjZjRcdWIwOThcdWNlNTgoUGlib25hY2NpKSBcdWMyMThcdWM1ZjRcdWM1ZDAgXHViMzAwXHVkNTc0IFx1YzBiNFx1ZDNiNFx1YmNmNFx1Yzc5MC4gXHVkNTNjXHViY2Y0XHViMDk4XHVjZTU4IFx1YzIxOFx1YzVmNFx1Yzc1OCBcdWM4MTBcdWQ2NTRcdWMyZGRcdWM3NDAgXHVjNTQ0XHViNzk4XHVjNjQwIFx1YWMxOVx1YjJlNC48XC9wPlxyXG48cD5QW25dICZuYnNwOz0gMSAoMCZsZTtuJmxlOyZwaTsgXHVjNzc4IFx1YWNiZFx1YzZiMCk8YnIgXC8+XHJcbiZuYnNwOz0gUFtuLTFdICsgUFtuLSZwaTtdIChcdWFkZjggXHVjNjc4XHVjNzU4IFx1YWNiZFx1YzZiMCk8XC9wPlxyXG48cD5cdWM4ZmNcdWM3NThcdWQ1NjAgXHVhYzgzXHVjNzQwIG5cdWM3NzQgXHVhZjJkIFx1YzgxNVx1YzIxOFx1Yzc3YyBcdWQ1NDRcdWM2OTRcdWIyOTQgXHVjNWM2XHViMmU0XHViMjk0IFx1YWM4M1x1Yzc3NFx1YjJlNC4gXHVjOTg5LCBQW24tJnBpO10gPSBQW24tJnBpOy0xXStQW24tJnBpOy0mcGk7XVx1YzY0MCBcdWFjMTlcdWM3NDAgXHVjMmRkXHVjNzNjXHViODVjIFx1YWNjNFx1YzBiMFx1Yzc0NCBcdWQ1NzQgXHVjOGZjXHVjNWI0XHVjNTdjIFx1ZDU1Y1x1YjJlNC48XC9wPlxyXG48cD5cdWM3OTBcdWM1ZjBcdWMyMThcdWI4NWMgblx1Yzc3NCBcdWM4ZmNcdWM1YjRcdWM4NGNcdWM3NDQgXHViNTRjLCBQW25dXHVjNzQ0IFx1YWQ2Y1x1ZDU1OFx1YjI5NCBcdWQ1MDRcdWI4NWNcdWFkZjhcdWI3YThcdWM3NDQgXHVjNzkxXHVjMTMxXHVkNTU4XHVjMmRjXHVjNjI0LjxcL3A+IiwiaW5wdXQiOiI8cD5cdWNjYWJcdWM5ZjggXHVjOTA0XHVjNWQwIFx1Yzc5MFx1YzVmMFx1YzIxOCBuKDEmbGU7biZsZTsxLDAwMClcdWM3NzQgXHVjOGZjXHVjNWI0XHVjOWM0XHViMmU0LjxcL3A+Iiwib3V0cHV0IjoiPHA+XHVjY2FiXHVjOWY4IFx1YzkwNFx1YzVkMCBQW25dXHVjNzQ0IFx1Y2Q5Y1x1YjgyNVx1ZDU1Y1x1YjJlNC4gXHVhYzEyXHVjNzc0IFx1YjllNFx1YzZiMCBcdWNlZTRcdWM5YzggXHVjMjE4IFx1Yzc4OFx1YzczY1x1YmJjMFx1Yjg1YyAxLDAwMCwwMDAsMDAwLDAwMCwwMDAsMDAwXHVjNzNjXHViODVjIFx1YjA5OFx1YjIwOCBcdWIwOThcdWJhMzhcdWM5YzBcdWI5N2MgXHVjZDljXHViODI1XHVkNTVjXHViMmU0LjxcL3A+IiwiaGludCI6IiIsIm9yaWdpbmFsIjoiMCIsInByb2JsZW1fbGFuZ19jb2RlIjoiXHVkNTVjXHVhZDZkXHVjNWI0In0seyJwcm9ibGVtX2lkIjoiMTczNyIsInByb2JsZW1fbGFuZyI6IjEiLCJ0aXRsZSI6IlBpYm9uYWNjaSIsImRlc2NyaXB0aW9uIjoiPHA+WW91IG1pZ2h0IGhhdmUgaGVhcmQgb2YgdGhlIEZpYm9uYWNjaSBudW1iZXJzIGFuZCBvZiB0aGUgbnVtYmVyIHBpLiBJZiB5b3UgbGV0IHRoZXNlIHR3byBpZGVhcyBtZXJnZSwgYSBuZXcgYW5kIGVzb3RlcmljIGNvbmNlcHQgY29tZXMgaW50byBiZWluZzogdGhlIFBpYm9uYWNjaSBudW1iZXJzLiBUaGVzZSBjYW4gYmUgZGVmaW5lZCBmb3IgcmVhbCB4Jmd0Oz0wIGJ5OjxcL3A+XHJcblxyXG48cD5QKHgpID0gMSZuYnNwOyZuYnNwOyAmbmJzcDtmb3IgMCZsdDs9eCZsdDs0PGJyIFwvPlxyXG5QKHgpID0gUCh4LTEpICsgUCh4LXBpKSZuYnNwOyZuYnNwOyAmbmJzcDtmb3IgNCZsdDs9eCw8XC9wPlxyXG5cclxuPHA+d2hlcmUgcGkgPSAzLjE0MTU5MjY1MzUuLi4gSW4gdGhpcyBwcm9ibGVtLCB5b3UgYXJlIGFza2VkIHRvIGNvbXB1dGUgUCh4KSBmb3IgYSBnaXZlbiB4LjxcL3A+XHJcbiIsImlucHV0IjoiPHA+VGhlIGlucHV0IGZpbGUgY29udGFpbnMgc2V2ZXJhbCBub24tbmVnYXRpdmUgcmVhbCBudW1iZXJzIGVhY2ggb24gYSBzZXBhcmF0ZSBsaW5lLiBUaGUgbGFzdCBsaW5lIGNvbnRhaW5zIC0xIG1hcmtpbmcgdGhlIGVuZCBvZiB0aGUgaW5wdXQgZmlsZS48XC9wPlxyXG5cclxuPHA+Jm5ic3A7PFwvcD5cclxuIiwib3V0cHV0IjoiPHA+Rm9yIGVhY2ggbm9uLW5lZ2F0aXZlIHJlYWwgbnVtYmVyIGluIHRoZSBpbnB1dCBmaWxlLCBvdXRwdXQgdGhlIGNvcnJlc3BvbmRpbmcgUGlib25hY2NpIG51bWJlci4gU2hvdWxkIHRoZSBQaWJvbmFjY2kgbnVtYmVyIGJlIG1vcmUgdGhhbiA1MCBkaWdpdHMgbG9uZywgZGl2aWRlIGl0IG9uIHRoZSBjb25zZWN1dGl2ZSBsaW5lcywgb3V0cHV0dGluZyA1MCBkaWdpdHMgb24gZWFjaCAodGhlIGxhc3QgbGluZSBtYXkgY29udGFpbiBsZXNzIGRpZ2l0cykuPFwvcD5cclxuXHJcbjxwPiZuYnNwOzxcL3A+XHJcbiIsImhpbnQiOiIiLCJvcmlnaW5hbCI6IjEiLCJwcm9ibGVtX2xhbmdfY29kZSI6Ilx1YzYwMVx1YzViNCJ9XQ==

출처

Contest > Internet Problem Solving Contest > IPSC 2001 F번

  • 문제를 번역한 사람: author5