[DP] 타일링

문제

가로 길이가 $N$인 $2 \times N$ 직사각형을 $1 \times 2$, $2 \times 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$

입출력 예시

입력: 5
출력: 8