[백준 JavaScript] 11726번 2×n 타일링

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

11726번: 2×n 타일링

 

<규칙>

2->2

3->3

4->5

5->8

 

solve(n) = solve(n-1) + solve(n-2)

 

<시간초과>

const input = require("fs").readFileSync("/dev/stdin").toString();
const num = Number(input);

const solve = (N) => {
  if (N === 1) {
    return 0;
  } else if (N === 2) {
    return 2;
  } else if (N === 3) {
    return 3;
  }
  return solve(N - 1) + solve(N - 2);
};

console.log(solve(num)%10007);

재귀로 풀었는데 시간초과 ㅜ

 

DP로 풀어야 됨!

 

<풀이방법>

const input = require("fs").readFileSync("/dev/stdin").toString();
const num = Number(input);

const DP = new Array(num + 1).fill(0);
DP[1] = 1;
DP[2] = 2;

for (let i = 3; i <= num; i++) {
  DP[i] = (DP[i - 1] + DP[i - 2]) % 10007;
}

console.log(DP[num]);

DP[num]을 10007로 나누니까 자꾸 틀렸다고 떴는데 나눈 값을 DP에 넣는거였습니다..