117272번 : 2xn 타일링 2

dp로 구성한다.

dp[i]는 2xi 직사각형을 2x1과 2x2 타일로 채우는 방법의 수이다.

1) i가 하나 늘어나면 세로로 된 2x1타일 하나밖에 올 수 없다.

2) i가 두 개 늘어나면 가로로 된 2x1타일 2개가 오는 경우와 2x2타일 1개가 오는 경우를 생각할 수 있다.

여기서 세로로 된 2x1타일 2개가 오는 경우는 이미 1)에서 확인 했으므로 배제한다.

#include <stdio.h>

#define R 10007

int dp[1001], N;

int main() {

scanf("%d", &N);

dp[0] = 1;

dp[1] = 1;

for (int i = 2; i <= N; ++i) {

dp[i] = (dp[i - 1]%R + dp[i - 2]*2%R)%R;

}

printf("%d", dp[N]%R);

} HACKED BY CHONGIN12