[BOJ] 11726 2×n 타일링 with JavaScript

JavaScript를 이용한 백준 11726 2×n 타일링 문제를 풀이한 글입니다.

문제

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

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

입력

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

출력

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

풀이

초기 접근

2x1 타일의 경우의 그냥 빈 곳에 넣으면 되지만 1x2 타일의 경우 한곳에 놓게 되면
무조건 2개를 놓아야 한다. 이를 생각해서 2x1을 a, 1x2 2개 묶음을 b로 생각해서
2x5 놓는다고 생각하면
b = 0 aaaaa
b = 1 aaab aaba abaa baaa
b = 2 abb bab bba
... => 이는 a와 b를 배치하는 중복 순열로 생각할 수 있다.
따라서 (a의 개수 + b의 개수)! / (a의 개수)! * (b의 개수)! 를
가능한 모든 b의 개수를 통해 계산해서 더하는 방식으로 해결할 수 있다.

실패

팩토리얼을 이용해 구하게 될 경우 숫자가 커질 경우
담을 수 있는 수의 범위를 초과하는 문제가 발생한다.
이를 해결하기 위해 모듈러 연산을 해당 계산식 안에 넣게 될 경우 코드가 굉장히 지저분하고 과정이 복잡해지는 문제가 발생한다. => 다른 방식으로 해결 필요

최종 접근

마지막에 놓은 타일이 2x1인 경우와 1x2인 경우를 나눠서 생각할 수 있다.
2x1 타일을 놓게 될 경우 2x(n-1) 타일에 올 수 있는 모든 경우가 존재할 수 있게 된다
1x2 타일을 놓게 되면 두개 묶음으로 놓게 되므로 2x(n-2) 타일에 올 수 있는 모든 경우가 존재 할수 있게 된다. 따라서 2xn의 타일은 2x(n-1)과 2x(n-2)타일에 올수 있는 경우의 합과 동일하다는 결론을 얻을 수 있다.
dp[1] = 1
dp[2] = 2
dp[n] = dp[n - 1] + dp[n - 2] 이 성립하게 되므로 아주 간단하게 해결할 수 있게 된다.

알고리즘

• 10,007로 나눈 나머지를 구해야 하므로 모든 dp[i]값에 % 10007을 진행한다.
• dp[0] = 0, dp[1] = 1, dp[2] = 2
• dp[i] = (dp[i-1] + dp[i-2]) % 10007 ( i = 3, 4 ... n)

구현

/**
 * https://www.acmicpc.net/problem/11726
 * 
 * 처음 생각: 2 x 1 타일의 경우 그냥 빈곳에 넣으면 되지만 
 * 1 x 2 타일의 경우 한곳에 놓게 되면 무조건 2개를 놓아야 한다.
 * 1 x 2 타일의 모양이 나타날수 있는 케이스를 생각하는 방식으로 접근
 * 1 x 2 타일 2개 묶음을 b
 * 1 x 2 타일 2개 묶음을 a 라고 하면
 * 2 x 5 의 경우 
 * b가 한번 오면 aaab aaba abaa baaa의 경우로 나타낼수 있다
 * => 중복이 존재하는 수열로 생각할 수 있음
 * (a의 개수 + b의 개수)! / (a의 개수)! * (b의 개수)!
 * b의 개수를 0부터 가능한 개수까지 차례대로 증가시켜 최대치까지 계산하고 모두 더한 값이 정답이 됨
 * => 1000!까지 계산해야 하는 경우가 발생하고 이를 해결하기 위해 modular를 중간에 넣기에는
 * 너무 복잡한 과정 => 다른 방식 필요
 * 
 * hint: DP 방식으로 보다간단하게 해결가능
 * n = 1 인경우 dp[1] = 1
 * n = 2 인경우 dp[2] = 2
 * ...
 * dp[n] => 마지막에 놓은 타일이 1x2 , 2x1 경우가 두가지가 존재한다.
 * 1x2 인경우 dp[n-2]의 경우의 수가 앞에 올수 있고
 * 2x1 인경우 dp[n-1]의 경우의 수가 앞에 올수 있다.
 * ===> 즉 dp[n] = dp[n-1] + dp[n-2]가 된다.
 */

const fs = require('fs');
const input = +fs.readFileSync('./input.txt').toString().trim();

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

console.log(dp[input]);