2xn 타일링

문제

• 백준 11726번 - 2xn 타일링

언어

• JavaScript

문제 풀이 step 1

• dp[n] = 2xn 크기의 직사각형을 1x2, 2x1 타일로 채우는 방법의 수
• 2xk 크기의 직사각형이 되기 위해서는 2x(k-1)크기의 직사각형에서 2x1 타일을 한 개 놓으면 되고, 2x(k-2)크기의 직사각형에서 1x2 타일을 두 개 놓으면 된다.
  • 2x1 타일 한 개 놓는 경우 (세로), dp[n-1]
  • 1x2 타일 두 개 놓는 경우 (가로), dp[n-2]
• 문제에서 10007로 나눈 값을 구하라고 했으므로 매 계산시 10007로 나눠준다.

소스 코드

const input = require("fs").readFileSync("/dev/stdin").toString().split("\n");
const MOD = 10007;

const solution = (input) => {
	const N = parseInt(input[0]);

	const dp = [];
	dp[0] = 1;
	dp[1] = 1;
	for (let i = 2; i <= N; i++) {
		dp[i] = (dp[i - 1] + dp[i - 2]) % MOD;
	}

	return dp[N];
};

console.log(solution(input));