[백준11727_자바스크립트(javascript)] - 2×n 타일링 2

🔴 문제

2×n 타일링 2

🟡 Sol

const fs = require('fs');
const path = process.platform === 'linux' ? '/dev/stdin' : 'Wiki\\input.txt';
const n = Number(fs.readFileSync(path));

const db = new Array(1001).fill(0);
db[1] = 1;
db[2] = 3;

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

🟢 풀이

⏰ 소요한 시간 : -

DP의 기본 유형이다. n이 1일때 경우 수는 1, 2일때 경우의 수는 3가지이다.
n이 3일때 경우의수는 왼쪽부터 덮개를 차례대로 채웠을 때 오른쪽의 빈 공간을 채우는 경우의수만 선택하면 된다. 조금 더 이해하기 쉽게 표현하면 우린 왼쪽부터 n-1/n-2위치까지 채워진 타일의 오른쪽에 타일을 추가하기만 하면 된다.
n이 3일때 자세히 살펴보자면, n-1위치까지 채워진 즉 n이 2일때 오른쪽에 2*1 타일 한장을 추가해주는 경우 밖에 없다. n-2위치까지 채워진 n이 1일때는 2*2인 타일로 채워주던가 혹은 1*2타일 두개로 채워주는 경우가 있다. 이 때 2*1타일 두장으로 채우는 경우는 n이 2일때 이미 고려를 해주었기 때문에 제외한다.
이를 점화식으로 세우면 다음과 같다.

db[n] = (db[n - 1] + 2 * db[n - 2])

이 문제는 값이 엄청 커질 수 있기 때문에 일반적으로 나머지 값을 출력하라고 한다. 따라서 DB에 저장 할 때 나눈 후 의 값을 저장해준다.

🔵 Ref

이것이 취업을 위한 코딩테스트다.