[JavaScript/DP] 백준 실버 3 : 1904 - 01타일

https://www.acmicpc.net/problem/1904

1904번: 01타일

---

📌 작성한 코드 

// 1904
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 = Array(N + 1);

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

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

console.log(dp[N]);

📌 설명 

정의 : dp[i] = 길이가 i일 때 타일로 만들 수 있는 이진수의 개수

점화식 : `dp[i] = dp[i-1] + dp[i-2]`

- i번째 수를 넣으려고 할 때 가능한 경우는 2가지이다.

- (1) dp[i-1]까지 만들어진 이진수에 1 더하기 (2) dp[i-2]까지 만들어진 이진수에 00 더하기 

- 2가지의 경우의 수를 고려해서 dp[i-1] + dp[i-2] 하면 dp[i]를 얻을 수 있다.

 

✅ 성공