11727 2×n 타일링 2

220503

알고리즘: DP

const fs = require('fs');
const filePath = process.platform === 'linux' ? 'dev/stdin' : '../input.txt';
const input = +fs.readFileSync(filePath).toString('utf-8');
const dp = [];
dp[1] = 1;
dp[2] = 3;
for (let i = 3; i <= input; i++) {
  dp[i] = (dp[i - 1] + 2 * dp[i - 2]) % 10007;
}
console.log(dp[input]);

221022

// 메모리 9660kb
// 시간 196ms
const n = +require('fs').readFileSync('dev/stdin');
const memo = { 1: 1, 2: 3 };

for (let i = 3; i <= n; i++) {
  memo[i] = (memo[i - 1] + 2 * memo[i - 2]) % 10007;
}

console.log(memo[n]);