[DP] 타일링

Time Limit: 1000 msMemory Limit: 256 MBBronze III2Author: 관리자

가로 길이가 $N$ 인 $2 \times N$ 직사각형을 $1 \times 2$ , $2 \times 1$ 도미노로 빈틈없이 덮는 방법의 수를 구하라. 답이 매우 클 수 있으니 로 나눈 나머지를 출력한다.

Problem Statistics

1

Total submissions

1

Accepted

100%

Acceptance rate

1

Unique solvers

2

×

1

1{,}000{,}000{,}007

$dp[n]$ 을 " $2 \times n$ 을 덮는 방법의 수"라 하면, 맨 오른쪽 칸을 세로 도미노 하나로 덮거나( $dp[n-1]$ ) 가로 도미노 두 개로 덮는다( $dp[n-2]$ ).

$dp[n] = dp[n-1] + dp[n-2], \quad dp[1] = 1, \; dp[2] = 2$

입력

첫 줄에 정수 $N$ ( $1 \le N \le 10^6$ ).

출력

방법의 수를 $1{,}000{,}000{,}007$ 로 나눈 나머지.

입력: 5
출력: 8