dp[n]
이라고 정의dp[0]
: 2x0 크기의 직사각형을 채우는 방법은 1개 (아무것도 채우지 않는 경우)dp[1]
: 2x1 크기의 직사각형을 채우는 방법은 1개 (2x1 타일 하나로 채우는 경우)2xn 직사각형을 채우는 방법을 두 가지로 나눌 수 있다.
이 두가지로 다음과 같은 점화식을 만들 수 있다.
dp[n] = dp[n−1] + dp[n−2]
const run = (numbers: number[]) => {
const result = [];
const maxNumber = Math.max(...numbers);
const dp = new Array(maxNumber + 1).fill(0);
dp[0] = 1;
dp[1] = 1;
for (let i = 2; i <= maxNumber; i++) {
dp[i] = (dp[i - 1] + dp[i - 2]) % 10007;
}
for (const number of numbers) {
result.push(dp[number]);
}
return result.join('\\n');
};
console.log(run(input));