시간 제한 메모리 제한 제출 정답 맞은 사람 정답 비율
1 초 128 MB 34 16 13 72.222%

문제

CTP마을에 사는 토끼 아람이는 3,2,1미터씩 뛰어서 n미터를 지난다. 람토끼가 지나야하야 하는 길이가 주어졌을 때 점프 길이가 증가하지 않는 순서로 지나가는 방법은 총 몇가지가 있을까?

찾을 수 있는 모든 경우의 수를 구하는 프로그램을 작성하시오.

입력

n이 표준입력으로 들어온다. (1 ≤ n ≤ 109)

출력

프로그램의 결과값을 표준출력으로 나타내시오. 값은 1000000으로 나눈 나머지를 출력하시오

예제 입력 1

6

예제 출력 1

7

힌트

1,2,3을 더해서 6이 되면서 증가하지 않는 수열로 이루어진 경우는 다음 7가지 이다. 7을 1000000으로 나눈 나머지인 7이 출력이 된다.

  1. 3+3
  2. 3+2+1
  3. 3+1+1+1
  4. 2+2+2
  5. 2+2+1+1
  6. 2+1+1+1+1
  7. 1+1+1+1+1+1
W3sicHJvYmxlbV9pZCI6IjMzNjAiLCJwcm9ibGVtX2xhbmciOiIwIiwidGl0bGUiOiJcdWFlNjFcdWNkMWRcdWFlNjFcdWNkMWQiLCJkZXNjcmlwdGlvbiI6IjxwPkNUUFx1YjljOFx1Yzc0NFx1YzVkMCBcdWMwYWNcdWIyOTQgXHVkMWEwXHViMDdjJm5ic3A7XHVjNTQ0XHViNzhjXHVjNzc0XHViMjk0IDMsMiwxXHViYmY4XHVkMTMwXHVjNTI5IFx1YjZmMFx1YzViNFx1YzExYyBuXHViYmY4XHVkMTMwXHViOTdjIFx1YzljMFx1YjA5Y1x1YjJlNC4gXHViNzhjXHVkMWEwXHViMDdjXHVhYzAwIFx1YzljMFx1YjA5OFx1YzU3Y1x1ZDU1OFx1YzU3YyBcdWQ1NThcdWIyOTQgXHVhZTM4XHVjNzc0XHVhYzAwIFx1YzhmY1x1YzViNFx1Yzg0Y1x1Yzc0NCBcdWI1NGMgXHVjODEwXHVkNTA0IFx1YWUzOFx1Yzc3NFx1YWMwMCBcdWM5OWRcdWFjMDBcdWQ1NThcdWM5YzAgXHVjNTRhXHViMjk0Jm5ic3A7XHVjMjFjXHVjMTFjXHViODVjJm5ic3A7XHVjOWMwXHViMDk4XHVhYzAwXHViMjk0IFx1YmMyOVx1YmM5NVx1Yzc0MCZuYnNwO1x1Y2QxZCBcdWJhODdcdWFjMDBcdWM5YzBcdWFjMDAgXHVjNzg4XHVjNzQ0XHVhZTRjPzxcL3A+XHJcblxyXG48cD5cdWNjM2VcdWM3NDQgXHVjMjE4IFx1Yzc4OFx1YjI5NCBcdWJhYThcdWI0ZTAgXHVhY2JkXHVjNmIwXHVjNzU4IFx1YzIxOFx1Yjk3YyBcdWFkNmNcdWQ1NThcdWIyOTQgXHVkNTA0XHViODVjXHVhZGY4XHViN2E4XHVjNzQ0IFx1Yzc5MVx1YzEzMVx1ZDU1OFx1YzJkY1x1YzYyNC48XC9wPlxyXG4iLCJpbnB1dCI6IjxwPm5cdWM3NzQgXHVkNDVjXHVjOTAwXHVjNzg1XHViODI1XHVjNzNjXHViODVjIFx1YjRlNFx1YzViNFx1YzYyOFx1YjJlNC4gKDEgJmxlOyBuICZsZTsgMTA8c3VwPjk8XC9zdXA+KTxcL3A+XHJcbiIsIm91dHB1dCI6IjxwPlx1ZDUwNFx1Yjg1Y1x1YWRmOFx1YjdhOFx1Yzc1OCBcdWFjYjBcdWFjZmNcdWFjMTJcdWM3NDQgXHVkNDVjXHVjOTAwXHVjZDljXHViODI1XHVjNzNjXHViODVjIFx1YjA5OFx1ZDBjMFx1YjBiNFx1YzJkY1x1YzYyNC4gXHVhYzEyXHVjNzQwIDEwMDAwMDBcdWM3M2NcdWI4NWMgXHViMDk4XHViMjA4IFx1YjA5OFx1YmEzOFx1YzljMFx1Yjk3YyBcdWNkOWNcdWI4MjVcdWQ1NThcdWMyZGNcdWM2MjQ8XC9wPlxyXG4iLCJoaW50IjoiPHA+MSwyLDNcdWM3NDQgXHViMzU0XHVkNTc0XHVjMTFjIDZcdWM3NzQgXHViNDE4XHViYTc0XHVjMTFjIFx1Yzk5ZFx1YWMwMFx1ZDU1OFx1YzljMCBcdWM1NGFcdWIyOTQgXHVjMjE4XHVjNWY0XHViODVjIFx1Yzc3NFx1YjhlOFx1YzViNFx1YzljNCBcdWFjYmRcdWM2YjBcdWIyOTQgXHViMmU0XHVjNzRjIDdcdWFjMDBcdWM5YzAgXHVjNzc0XHViMmU0LiA3XHVjNzQ0Jm5ic3A7MTAwMDAwMFx1YzczY1x1Yjg1YyBcdWIwOThcdWIyMDggXHViMDk4XHViYTM4XHVjOWMwXHVjNzc4IDdcdWM3NzQgXHVjZDljXHViODI1XHVjNzc0IFx1YjQxY1x1YjJlNC48XC9wPlxyXG5cclxuPG9sPlxyXG5cdDxsaT4zKzM8XC9saT5cclxuXHQ8bGk+MysyKzE8XC9saT5cclxuXHQ8bGk+MysxKzErMTxcL2xpPlxyXG5cdDxsaT4yKzIrMjxcL2xpPlxyXG5cdDxsaT4yKzIrMSsxPFwvbGk+XHJcblx0PGxpPjIrMSsxKzErMTxcL2xpPlxyXG5cdDxsaT4xKzErMSsxKzErMTxcL2xpPlxyXG48XC9vbD5cclxuIiwib3JpZ2luYWwiOiIwIiwicHJvYmxlbV9sYW5nX2NvZGUiOiJcdWQ1NWNcdWFkNmRcdWM1YjQifSx7InByb2JsZW1faWQiOiIzMzYwIiwicHJvYmxlbV9sYW5nIjoiMSIsInRpdGxlIjoiSnVtcHMiLCJkZXNjcmlwdGlvbiI6IjxwPkEgYnVubnkgaGFzIHRvIHBhc3MgbiBtZXRlcnMgd2l0aCBqdW1wcyBvZiBsZW5ndGhzIDMsIDIgb3IgMSBtZXRlcnMuIEluIGhvdyBtYW55IGRpZmZlcmVudCB3YXlzIHRoaXMgY2FuIGJlIGRvbmUsIGlmIHRoZSBsZW5ndGhzIG9mIHN1Y2Nlc3NpdmUganVtcHMgZm9ybSBhIG5vbi1pbmNyZWFzaW5nIHNlcXVlbmNlPyBXcml0ZSBwcm9ncmFtIGp1bXBzLCB3aGljaCBjb21wdXRlcyB0aGUgbnVtYmVyIHdlIGFyZSBsb29raW5nIGZvci48XC9wPlxyXG4iLCJpbnB1dCI6IjxwPlRoZSB2YWx1ZSBvZiBuIHNob3VsZCBiZSBlbnRlcmVkIGZyb20gdGhlIHN0YW5kYXJkIGlucHV0ICgxICZsZTsgbiAmbGU7IDEwPHN1cD45PFwvc3VwPikuPFwvcD5cclxuIiwib3V0cHV0IjoiPHA+VGhlIHByb2dyYW0gc2hvdWxkIHdyaXRlIHRvIHRoZSBzdGFuZGFyZCBvdXRwdXQgb25lIGludGVnZXIsIGVxdWFsIHRvIHRoZSByZW1haW5kZXIgb2YgdGhlIGZvdW5kIG51bWJlciwgZGl2aWRlZCBieSAxMDAwMDAwLjxcL3A+XHJcbiIsImhpbnQiOiI8cD5UaGUgbnVtYmVyIG9mIGRpZmZlcmVudCB3YXlzIGlzIDcsIGFuZCBpdHMgcmVtYWluZGVyIG1vZHVsbyAxMDAwMDAwIGlzIGFsc28gNy4gVGhlIGRpZmZlcmVudCBzZXF1ZW5jZXMgb2YganVtcHMgYXJlOjxcL3A+XHJcblxyXG48b2w+XHJcblx0PGxpPjMrMzxcL2xpPlxyXG5cdDxsaT4zKzIrMTxcL2xpPlxyXG5cdDxsaT4zKzErMSsxPFwvbGk+XHJcblx0PGxpPjIrMisyPFwvbGk+XHJcblx0PGxpPjIrMisxKzE8XC9saT5cclxuXHQ8bGk+MisxKzErMSsxPFwvbGk+XHJcblx0PGxpPjErMSsxKzErMSsxJm5ic3A7PFwvbGk+XHJcbjxcL29sPlxyXG4iLCJvcmlnaW5hbCI6IjEiLCJwcm9ibGVtX2xhbmdfY29kZSI6Ilx1YzYwMVx1YzViNCJ9XQ==

출처

Olympiad > Junior Balkan Olympiad in Informatics > JBOI 2008 4번