[백준]11726번 - 2xn타일링
2022년 03월 01일
[해결 코드]
const fs = require("fs");
let input = fs.readFileSync("/dev/stdin").toString()
const N = +input;
const DP = new Array(N + 1).fill(0);
DP[1] = 1;
DP[2] = 2;
for (let i = 3; i < N + 1; i++) {
DP[i] = (DP[i - 1] + DP[i - 2]) % 10007;
}
console.log(DP[N]);[풀이]
1. N이 1부터 경우의 수를 나열해보니 1,2,3,5,8,13… 피보나치 수열임을 알 수 있었다.
다음과 같은 점화식을 이용하면 해결할 수 있다.
DP[i] = DP[i-1] + DP[i-2]2. 직접 타일을 그려보니 규칙을 발견할 수 있었다. n번 째 타일에는 n-1번 째 타일이 들어가는 경우와 n-2번 째 타일이 들어가는 경우의 합임을 캐치해내면 DP로 구현할 수 있다.
Tags