2 x n 타일링 1

문제

2×n 크기의 직사각형을 1×2, 2×1 타일로 채우는 방법의 수를 구하는 프로그램을 작성하시오.

아래 그림은 2×5 크기의 직사각형을 채운 한 가지 방법의 예이다.

입력

첫째 줄에 n이 주어진다. (1 ≤ n ≤ 1,000)

출력

첫째 줄에 2×n 크기의 직사각형을 채우는 방법의 수를 10,007로 나눈 나머지를 출력한다.

예제 입력 1

2

예제 출력 1

2

예제 입력 2

9

예제 출력 2

55

나의 코드

const input = require("fs").readFileSync("/dev/stdin").toString().trim();

let dp = [0, 1, 2];

for (let i = 3; i <= input; i++) {
  dp[i] = (dp[i - 1] + dp[i - 2]) % 10007;
}
console.log(dp[input]) % 10007;

n이 2만큼 증가할 때 타일을 추가하는 방법
- 2x1 타일 2개 추가 (경우의 수는 달라지지 않음)
n이 1만큼 증가할 때 타일을 추가하는 방법
- 1x2 타일 1개 추가 (경우의 수는 달라지지 않음)

다르게 말하면, input으로 들어온 숫자 n이 주어졌을 때 타일로 직사각형을 만드는 경우의 수는 n - 2였을 때 경우의 수 + n - 1이었을 때 경우의 수와 같다.

2 x n 타일링 2

문제

2×n 직사각형을 1×2, 2×1과 2×2 타일로 채우는 방법의 수를 구하는 프로그램을 작성하시오.

아래 그림은 2×17 직사각형을 채운 한가지 예이다.

입력

첫째 줄에 n이 주어진다. (1 ≤ n ≤ 1,000)

출력

첫째 줄에 2×n 크기의 직사각형을 채우는 방법의 수를 10,007로 나눈 나머지를 출력한다.

예제 입력 1

2

예제 출력 1

3

예제 입력 2

8

예제 출력 2

171

예제 입력 3

12

예제 출력 3

2731

나의 코드

const input = Number(
  require("fs").readFileSync("/dev/stdin").toString().trim()
);

let dp = [0, 1, 3];
for (let i = 3; i <= input; i++) {
  dp[i] = (2 * dp[i - 2] + dp[i - 1]) % 10007;
}
console.log(dp[input]);

n이 2만큼 증가할 때 타일을 추가하는 방법
- 2x1 타일 2개 추가 (경우의 수는 달라지지 않음)
- 2x2 타일 1개 추가 (경우의 수는 달라지지 않음)
n이 1만큼 증가할 때 타일을 추가하는 방법
- 1x2 타일 1개 추가 (경우의 수는 달라지지 않음)

다르게 말하면, input으로 들어온 숫자 n이 주어졌을 때 타일로 직사각형을 만드는 경우의 수는 (n - 2였을 때 경우의 수) * 2 + (n - 1이었을 때 경우의 수)와 같다.

어제 아무리 붙잡고 있어도 못 풀다가 오늘 문득 수가 증가하는 패턴이 보여서 통과는 할 수 있었지만, 이코테 책을 참고하고나서야 정확한 논리를 알게 되었다. 기본적인 점화식을 보여준다. 이래서 전형적인 DP문제라고 하는군! 더 많은 문제를 풀어보자 화이팅!!