문제 2017

블록 놓기

시간 제한 1.000초 메모리 제한 128MB

제출

바로가기

문제를 해결할 코드를 제출합니다.

정답 수

1

제출 수

10

정답률

10.0%

문제 설명

연속하는 총 \(N\)개의 칸이 다음과 같이 있다.

각 위치에 블록을 쌓는 놀이를 하려고 한다. 이때, 다음과 같은 규칙이 있다.

• 첫 칸과 마지막 칸은 블록이 없어야 한다.
• 인접한 칸과의 블록 개수 차이는 \(1\) 이하여야 한다.

칸의 개수 \(N\)이 주어졌을 때, 쌓을 수 있는 경우의 수를 구하여라.
단, 수가 커질 수 있으므로 \(10^9+7\)로 나눈 나머지를 출력하시오.

입력 설명

칸의 개수 \(N\)이 자연수로 주어진다.
\((1 \le N \le 5000)\)

출력 설명

쌓을 수 있는 경우의 수를 \(10^9+7\)로 나눈 나머지를 출력한다.

입력 예시

3

출력 예시

2

힌트

다이나믹 프로그래밍

출처

jbs33_PJW