https://www.acmicpc.net/problem/11727
11727번: 2×n 타일링 2
2×n 직사각형을 1×2, 2×1과 2×2 타일로 채우는 방법의 수를 구하는 프로그램을 작성하시오. 아래 그림은 2×17 직사각형을 채운 한가지 예이다.
www.acmicpc.net
📌 작성한 코드
//11727
const fs = require("fs");
const filePath = process.platform === "linux" ? "/dev/stdin" : "Beakjoon/Silver/test.txt";
let input = fs.readFileSync(filePath).toString().trim();
const N = Number(input);
const dp = new Array(N + 1);
dp[1] = 1;
dp[2] = 3;
for (let i = 3; i <= N; i++) {
dp[i] = (dp[i - 2] * 2 + dp[i - 1]) % 10007;
}
console.log(dp[N]);
📌 설명
정의 : dp[i] - i 번째 열까지 왔을 때 블럭을 채울 수 있는 경우의 수
점화식 : `dp[i] = dp[i-2] * 2 + dp[i-1]`

✅ 성공

'알고리즘 > 백준' 카테고리의 다른 글
| [JavaScript/Greedy] 백준 골드 5 : 2170 - 선긋기 (1) | 2024.02.19 |
|---|---|
| [JavaScript/Greedy] 백준 골드 5 : 11000 - 강의실 배정 (0) | 2024.02.19 |
| [JavaScript/DP] 백준 실버 2 : 1912 - 연속합 (0) | 2024.02.17 |
| [JavaScript/DP] 백준 실버 1 : 1932 - 정수 삼각형 (0) | 2024.02.16 |
| [JavaScript/DP] 백준 실버 3 : 1003 - 피보나치 함수 (0) | 2024.02.16 |