바닥공사

문제

풀이

• N이 1일때, 2일때, 3일때, 4일때 경우를 찾는다.
• N * 2
• 1 * 2 = 1 |
• 2 * 2 = 3 || ,〓 ,ㅁ -> 조합
• 3 * 2 = 5 |||, |〓 , |ㅁ,〓|, ㅁ| (|)||, (|)〓 , (|)ㅁ, (〓)|, (ㅁ)|
• 4 * 2 = 11 1,3 조합 & 22 조합 =>
• (|)|||, (|)|〓 , (|)|ㅁ,(|)〓|, (|)ㅁ|
• (〓)|| ,(〓)〓 ,(〓)ㅁ,
• (ㅁ)|| ,(ㅁ)〓 ,(ㅁ)ㅁ
• ||인경우는, 무조건 옆에 |만 들어가서, (||)|| ,(||)〓 ,(||)ㅁ, -> 중복되는 애들은.. 어차피 |의 경우 |만들어간다!! 결국 |경우와 같은것.

  // 즉 f(n-1)x3 이 아니라 f(n-1)x2 이다 !! <- 이부분 주의하라..!

코드

// N * 2
// 1 * 2 = 1 |
// 2 * 2 = 3 || ,〓 ,ㅁ -> 조합
// 3 * 2 = 5 |||, |〓 , |ㅁ,〓|,  ㅁ|      (|)||, (|)〓 , (|)ㅁ, (〓)|,  (ㅁ)|
// 4 * 2 = 11  1,3 조합 & 22 조합 =>
// (|)|||, (|)|〓 , (|)|ㅁ,(|)〓|,  (|)ㅁ|
//  (〓)|| ,(〓)〓 ,(〓)ㅁ, (ㅁ)|| ,(ㅁ)〓 ,(ㅁ)ㅁ     (||)|| ,(||)〓 ,(||)ㅁ, -> 중복되는 애들은.. 어차피 |의 경우 |만들어간다!! 결국 |경우와 같은것.
// 즉 *3 이 아니라 *2 이다 !! <- 이부분 주의하라..!
function floor(N) {
  const dp = Array.from({ length: N + 1 }, () => 0);
  dp[1] = 1;
  dp[2] = 3;
  for (let x = 3; x <= N; x++) {
    dp[x] = dp[x - 1] + dp[x - 2] * 2;
  }
  return dp[N];
}

console.log(floor(3));