[백준, node.js] 11726번 "2xn 타일링" 문제 해결방법

[백준, node.js] 11726번 "2xn 타일링" 문제 해결방법

문제

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

예제 입력 & 출력

예제 입력, 출력 예시

소스코드

"2xn 타일링" 문제는 다이나믹 프로그래밍(DP, 동적계획법)을 활용해서 풀 수 있는 문제입니다. 사용할 수 있는 타일은 1x2, 2x1 두 가지 타일 타입이 존재합니다. 아래는 n이 4일 경우에 대한 예시입니다. n이 1일 경우 2x1 타일 하나만 사용이 가능하기 때문에 1, n이 2일 경우 1x2 타일 2개, 2x1 타일 2개를 사용해서 총 2개의 경우의 수를 낼 수 있습니다.

2x3부터 패턴을 잘 살펴보시면 되는데 아래 그림의 오른쪽 색상으로 표시한 직사각형을 살펴보면 우측에 2x1 타일이 들어갈 경우와 2x1 타일 2개가 들어간 패턴을 확인할 수 있습니다. 2x1 타일을 우측에 배치했을 경우 n-1의 결과값과 같고, 1x2 타일을 우측에 배치했을 경우 n-2 결과값과 같은 점을 캐치했다면 DP로 구현할 수 있음을 알 수 있습니다.

memo[i] = memo[i - 1] + memo[i - 2]

const fs = require('fs');
let count = Number(fs.readFileSync('./dev/stdin').toString());
const memo = {
  1: 1,
  2: 2
}

for (let i = 3; i <= count; i++) {
  memo[i] = (memo[i - 1] + memo[i - 2]) % 10007;
}

console.log(memo[count]);