https://www.acmicpc.net/problem/1904
1904번: 01타일
지원이에게 2진 수열을 가르쳐 주기 위해, 지원이 아버지는 그에게 타일들을 선물해주셨다. 그리고 이 각각의 타일들은 0 또는 1이 쓰여 있는 낱장의 타일들이다. 어느 날 짓궂은 동주가 지원이
www.acmicpc.net
📌 작성한 코드
// 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]를 얻을 수 있다.
✅ 성공

'알고리즘 > 백준' 카테고리의 다른 글
| [JavaScript/BFS/백트래킹] 백준 골드 3 : 1941 - 소문난 7공주 (1) | 2024.02.28 |
|---|---|
| [JavaScript] 백준 골드 5 - 2293 : 동전 1 (solve X) (1) | 2024.02.28 |
| [JavaScript/DP] 백준 골드 5 : 15486 - 퇴사 2 (2) | 2024.02.28 |
| [JavaScript/DP] 백준 골드 5 : 17070 - 파이프 옮기기 1 (1) | 2024.02.27 |
| [JavaScript/DP] 백준 골드 5 : 2011 - 암호 코드 (1) | 2024.02.26 |