On this page

백준 11726 JavaScript

On this page

문제
풀이

문제

백준 11726 - 2xn 타일링

풀이

이 문제도 메모제이션을 이용해 풀었다.
2Xn으로 타일링을 하면 맨 처음 채워지는 타일은 2x1 타일 하나 또는 1x2 타일일 것이다.
그 이후로 타일이 배치되는 경우의 수는

2x1 타일이 처음 나온 경우를 제외해 가로 길이- 1인 경우
1x2 타일이 처음 나온 경우를 제외해 가로 길이 -2인 경우

로 재귀적으로 계산을 할 수 있다.

const readFileSyncPath = require('path').basename(__filename).replace(/js$/, 'txt');
// const readFileSyncPath = '/dev/stdin';
const N = parseInt(require('fs').readFileSync(readFileSyncPath).toString().trim());

const DP = new Array(N + 1).fill(0);
const MOD = 10007;

const tiling = width => {
  if (width <= 1) return 1;

  if (DP[width] !== 0) return DP[width];

  DP[width] = (tiling(width - 1) + tiling(width - 2)) % MOD;

  return DP[width];
}

console.log(tiling(N));

Edit this page

Last updated on 3/2/2022

Tags

백준 11726 JavaScript

문제

풀이