문제 설명
계단 앞에 선 세종이는 그냥 계단을 오르기에는 지루하다고 생각하여 다양한 방법으로 계단을 올라갔다가 다시 내려오는 다양한 경우를 생각해보았다.
세종이는 한 번에 최대 3칸까지 올라갈 수 있다. 마지막 단까지 올라가면 다시 내려와야 한다. 내려올 때에는 한 번에 최대 4칸까지 내려올 수 있다.
이 규칙을 지키면서 계단을 올라갔다가 내려올 때 세종이가 올라갈 때 밟았던 계단을 밟지 않으면서 내려올 수 있는 방법의 경우의 수를 구하고자 한다.
만약 세종이가 2칸의 단으로 구성된 계단을 올라갔다 내려오는 경우는 다음과 같이 총 3가지 방법이 존재한다.
올라갈 때: (0), 1, (2) 내려올 때: (2), (0)
올라갈 때: (0), (2) 내려올 때: (2), (0)
올라갈 때: (0), (2) 내려올 때: (2), 1, (0)
*() 괄호로 묶인 숫자는 바닥과 가장 마지막 계단을 의미하며, 반드시 밟아야 한다.
계단을 구성하는 단의 수가 주어질 때 세종이가 올라갔다 내려오는 모든 경우의 수를 구하는 프로그램을 작성하시오.
세종이는 한 번에 최대 3칸까지 올라갈 수 있다. 마지막 단까지 올라가면 다시 내려와야 한다. 내려올 때에는 한 번에 최대 4칸까지 내려올 수 있다.
이 규칙을 지키면서 계단을 올라갔다가 내려올 때 세종이가 올라갈 때 밟았던 계단을 밟지 않으면서 내려올 수 있는 방법의 경우의 수를 구하고자 한다.
만약 세종이가 2칸의 단으로 구성된 계단을 올라갔다 내려오는 경우는 다음과 같이 총 3가지 방법이 존재한다.
올라갈 때: (0), 1, (2) 내려올 때: (2), (0)
올라갈 때: (0), (2) 내려올 때: (2), (0)
올라갈 때: (0), (2) 내려올 때: (2), 1, (0)
*() 괄호로 묶인 숫자는 바닥과 가장 마지막 계단을 의미하며, 반드시 밟아야 한다.
계단을 구성하는 단의 수가 주어질 때 세종이가 올라갔다 내려오는 모든 경우의 수를 구하는 프로그램을 작성하시오.
입력 설명
단의 수를 나타내는 자연수 \(n\)이 주어진다.
\((1 \le n \le 10,000)\)
\((1 \le n \le 10,000)\)
출력 설명
조건을 만족하는 경우의 수를 1,000,000,007(10억7)로 나눈 나머지를 출력한다.
입력 예시 Copy
2
출력 예시 Copy
3