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

🔴 문제

2×n 타일링

🟡 Sol

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

const dp = Array(n + 1).fill(0);

dp[1] = 1;
dp[2] = 2;


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

console.log(dp[n]);

🟢 풀이

⏰ 소요한 시간 : -

dp의 기본 문제 유형이다.
왼쪽부터 타일을 차곡 차곡 채워 넣었을 때, 오른쪽에 너비가 2짜리 타일을 채우는 경우, 1짜리 타일을 채우는 경우 두가지경우를 더해주면 된다.
너비가 1일 경우 채울 수 있는 가짓수는 1 이므로 dp[1] = 1,
너비가 2일 경우 채울 수 있는 가짓수는 2이므로 dp[2] = 2,
너비가 3일 경우에는 너비가 2일 경우의 끝에 타일 한 장 붙인 것과 너비가 1일 경우의 끝에 타일 한 장 붙인것 즉 dp[1] + dp[2] 가 된다.
따라서 점화식을 아래와 같이 세워주고 문제 요구사항에 맞도록 10007로 나누어 주면 된다.

dp[i] = (dp[i - 1] + dp[i - 2]) % 10007;

🔵 Ref