시간 제한 메모리 제한 제출 정답 맞은 사람 정답 비율
1 초 128 MB 26 12 9 69.231%

문제

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

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

입력

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

출력

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

예제 입력

6

예제 출력

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

출처

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