[백준] 11726

2×n 타일링

문제

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

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

입력

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

출력

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

풀이

const twoN = () => {
  let n = parseInt(require("fs").readFileSync("/dev/stdin").toString().trim());
  let dp = Array.from({ length: n }, (v) => 0);
  dp[0] = 1;
  dp[1] = 2;
  for (let i = 2; i < n; i++) {
    dp[i] = (dp[i - 2] + dp[i - 1]) % 10007;
  }
  console.log(dp[n - 1]);
};

twoN();

반성회

테이블 정의하기

D[i] = 2 * i 크기의 직사각형을 채우는 방법의 수

점화식 찾기

2 * 1 크기의 직사각형으로 채우는 방법은 하나의 직사각형을 세로로 배치하거나, 두 개의 직사각형을 가로로 배치하는 두 가지 경우가 있다

하나의 직사각형을 세로로 배치하면 가로 1칸만큼 키울 수 있고, 두개의 직사각형을 가로로 배치하면 가로 2칸만큼 키울 수 있으므로 이를 이용하면 된다

그렇다는 것은 D[N] 을 구하기 위해 D[N - 1] 과 D[N - 2] 가 필요하다는 것을 알 수 있다

2 * (N - 2) 의 직사각형을 채우는 경우의 수가 D[N - 2]가지라면, 2 * N 크기의 직사각형을 채우려면 2 * (N - 2) 크기를 먼저 채우고 나서 가로로 2개를 더 배치하면 된다 = 경우의 수 D[N - 2]가지

세로로 2개를 배치하는 것도 답처럼 보이긴 하지만 그 경우는 2 * (N - 1) 크기 직사각형을 채웠을 때 이미 카운트되기 때문에 중복된 결과를 낳는다

2 * (N - 1) 의 직사각형을 채우는 경우의 수가 D[N - 1] 가지라면, 그 상태에서 세로로 직사각형을 1개 배치하면 된다 = 경우의 수 D[N - 1]가지

따라서 2 * N 크기의 직사각형을 채우려면 2 * (N - 1) 크기의 직사각형과 2 * (N - 2) 크기의 직사각형을 채우는 경우의 수를 더한 것과 같다

D[N] = D[N - 1] + D[N - 2]

초기값 정하기

위 점화식으로 풀 수 있는 N의 최소값이 2이므로, (N번째 값을 구하려면 N - 1번째 값과 N - 2번째 값이 필요함) 적어도 D[0], D[1] 의 값을 알아야 풀 수 있다

D[0] 은 2 * 1 크기의 직사각형을 채우는 가짓수로, 2 * 1 직사각형을 세로로 하나 배치하면 되기 때문에 1이다

D[1] 은 2 * 2 크기의 직사각형을 채우는 가짓수로, 2 * 1 직사각형을 세로로 2개 배치하거나 가로로 2개 배치하면 되기 때문에 2이다

풀기

위의 점화식이 굉장히 간단하기 때문에 그대로 for문에 적용한 후 D[n - 1] (N번째) 까지 경우의 수를 계산한다

D[n - 1]을 그대로 출력하면 최소값의 총합이 된다