Informatica Online Judge

  숏다리의 계단오르기 [1061 / 0425]

Time Limit(Test case) : 1000 (ms)
Number of users who solved : 319   Total Tried : 584


The Champion of this Problem (C++) : gs16109 - ms / 178byte
My Best Submission (C++) : N/A

[JKJeong 2014]

Background

다리가 짧은 경곽이는 다리가 긴 영재가 한 번에 3칸 씩 계단을 올라가는 모습을 보고 자기도 3칸을 올라갈 수 있다고 생각했다.

야심차게 도전하여 한 번에 3칸을 올라갔으나, 한 번에 너무 힘을 써서 그 후로는 3칸을 올라갈 엄두를 내지 못했다.

하지만 3칸을 올라간 후, 두 번은 그냥 쉽게 1칸 또는 2칸을 이동하니 다시 힘이 회복되어 3칸을 올라갈 수 있을 것 같았다. ^^;

결론은 경곽이는 계단을 오를 때, 한 번에 한 칸 혹은 두 칸은 조건없이 오를 수 있다. 하지만 세 칸을 오르기 위해서는 마음의 준비가 필요하다. 즉 한 번 세 칸을 오르고 나면 적어도 다음 2번의 이동에서는 세 칸을 오를 수 없다.

즉 경곽이가 계단을 8칸을 올라간다고 가정하자.

1 1 1 1 1 1 1 1

이는 모두 1칸씩 이동하여 8칸을 이동한 예이다. 이건 경곽이가 할 수 있는 방법이다.

그리고

3 1 2 1 1

이것도 가능하다.

1 2 1 2 2

물론 이렇게도 올라갈 수 있다.

하지만

3 3 2, 2 3 3, 3 2 3

등은 불가능하다.

왜냐하면 짧은 다리로 3칸을 한 번 올라가면 적어도 다음 2번의 이동에서는 3칸을 오를 수 없다는 조건 때문이다.

따라서 8칸의 계단이 있을 때, 3칸 오르기 신공을 2번 사용하는 방법은

3 1 1 3

이 방법 뿐이다.

계단의 수 N이 주어질 때, 경곽이가 계단을 올라갈 수 있는 서로다른 방법의 수를 모두 구하는 프로그램을 작성하시오.

단, 수가 너무 커지기 때문에 경곽이가 계단을 올라갈 수 있는 수를 10억 7로 나눈 나머지를 출력하시오.

Input

첫 번째 줄에 N이 입력된다.

[입력값의 정의역]
1 <= N <= 10,000


[Sub-Task Info]
#1 : N < 10
#2 : N < 20
#3 : N <= 1010
#4 : 추가제한조건 없음.

(각 25점씩)

* 입력값이 클 때, 시간초과에 걸리지 않는 알고리즘을 설계할 수 있도록 하세요.

Output

경곽이가 계단을 오를 수 있는 모든 경우의 수를 10억 7로 나눈 나머지를 출력한다.

IO Example

입력
4

출력
7

* 4칸의 계단을 오르는 방법은

- 1 1 1 1
- 1 1 2
- 1 2 1
- 2 1 1
- 2 2
- 1 3
- 3 1

으로 모두 7가지이다.

Submit : [C/C++] | [C++11] | [Obj-C] | [Java] | [Python]
Prob Analysis : [Problem Statistics] | [Solution]