주의사항
Top Down 형식으로 풀때 memoization을 해줘야지 시간초과가 발생하지 않음
출력 할때 모든 계산을 한 뒤 나머지 연산을 하면 범위를 초과해서 오버플로우 발생하므로 매번 나머지 연산을 한 뒤 값을 저장해야함
풀이코드
Top Down
let dp = [];
let input = [];
var require = require("readline")
.createInterface(process.stdin, process.stdout)
.on("line", function(line) {
input.push(line.trim());
})
.on("close", function() {
let k = Number(input[0])
dp[0] = 1;
dp[1] = 1;
console.log(tiling(input));
});
const tiling = input => {
if (dp[input] > 0) {
return dp[input];
}
dp[input] = (tiling(input - 2) + tiling(input - 1)) % 10007;
return dp[input];
};
Bottom Up
let dp = [];
let input = [];
var require = require("readline")
.createInterface(process.stdin, process.stdout)
.on("line", function(line) {
input.push(line.trim());
})
.on("close", function() {
let k = Number(input[0])
dp[0] = 1;
dp[1] = 1;
for (let i = 2; i < k + 1; i++) {
dp[i] = (dp[i - 2] + dp[i - 1])%10007;
}
console.log(dp[k]);
});