[백준1793_자바스크립트(javascript)] - 타일링

🔴 문제

타일링

🟡 Sol

const fs = require('fs');
const path = process.platform === 'linux' ? '/dev/stdin' : 'input.txt';
const inputs = fs.readFileSync(path).toString().trim().split('\n').map(Number);
const n = Math.max(...inputs);
const dp = Array(n + 1).fill(1n);

dp[1] = 1n;
dp[2] = 3n;

for (let i = 3; i <= n; i++) {
  dp[i] = dp[i - 1] + dp[i - 2] * 2n;
}

for (const input of inputs) {
  console.log(dp[input].toString());
}

🟢 풀이

⏰ 소요한 시간 : -

dp의 기본 유형인 타일링을 복습하기 위해서 풀어보았다!
n의 최대값은 250이니까 250 크기의 dp배열을 만들어 준다.
n이 1일때는 2*1타일을 세우는 경우, n이 2일때는 2*1를 두 개 세우는 경우, 두 개 눕히는 경우, 2*2타일 하나로 채우는 경우 3개가 된다.
n이 3인 경우는 n이 2일때의 모든 경우의 수에 2*1을 하나 세우는 경우들과 n이 1일때의 모든 경우의 수에 2*2타일하나르 붙이는 경우들과 n이 1일때의 모든 경우의 수에 2*1타일을 두 개 눕히는 경우들이 있다.
이를 모두 계산해 dp 배열을 채우면 다음과 같다.

 dp[i] = dp[i - 1] + dp[i - 2] * 2n;

참고로 큰 값이 나오니 BigInt로 연산한다.

🔵 Ref