타일링 시리즈

• LV1. 11726: 2xn 타일링
• LV2. 11727: 2xn 타일링 2
• LV3. 2133: 타일 채우기
• LV4. 14852: 타일 채우기 3
• LV5. 아방가르드 타일

문제

https://www.acmicpc.net/problem/11726
2×n 크기의 직사각형을 1×2, 2×1 타일로 채우는 방법의 수를 구하는 프로그램을 작성하시오.
아래 그림은 2×5 크기의 직사각형을 채운 한 가지 방법의 예이다.

풀이

이전문제 에서는 타일이 2x1 1x2 밖에 없었다 하지만 이번엔 2x2가 새로 생겼다.
그래서 n이 1일때 경우의 수는 그대로이고 n이 2일때 사각형 모양이 하나 더 생기게 되었다.

이전에 풀었던 방식처럼 n이 1일떄 ~ 4일때, 그리고 x일때를 그려보면 아래와 같다.

n이 1일때는 새로 생긴 도형이 한개, 2일때는 새로 생긴 도형이 2개다.
그래서 이번 점화식은 아래와 같이 된다.

dp[i] = n 이 i일 때 그릴 수 있는 모형의 개수,
dp[1] = 1, dp[2] = 2;
dp[i] = ( dp[i-1] + dp[i-2] * 2 ) % 10007

코드

//const stdin = require('fs').readFileSync(0, 'utf8').trim().split('\n');
const stdin = `4`.trim().split('\n');

const N = +stdin[0];
const dp = Array(1001).fill(0);
dp[1] = 1;
dp[2] = 3;

for (let i = 3; i <= N; i++) {
  dp[i] = (dp[i - 1] + dp[i - 2] * 2) % 10007;
}

console.log(dp[N]);