백준 2133번: 타일 채우기 - javascript

백준 2133번: 타일 채우기

문제 설명

3×N 크기의 벽을 2×1, 1×2 크기의 타일로 채우는 경우의 수를 구해보자.

입력

첫째 줄에 N(1 ≤ N ≤ 30)이 주어진다.

출력

첫째 줄에 경우의 수를 출력한다.

접근

그러니깐 이런 형식으로 네모를 채우라는 문제인데…
먼저 홀수인 경우에는 무조건 0이다. 어떤 방법으로도 채울 수 없다. 2xN타일 문제랑 비슷한 줄 알았는데 복병이 있다.
바로 요렇게 생긴놈.

요녀석은 n이 4이상인 경우부터 생기는 형태다.
n이 6이면 이런 형태도 나온다.

즉 n이 4이상이면 이런 스페셜한 친구들이 나온다…
그 외에는 우리가 생각 할 수 있는 3가지 친구들의 바리에이션이다.

아무튼 n=4부터는 저런 독특한 바리에이션 덕분에 +2를 하게된다.
먼저 4보다 작은 짝수는 2이므로 4-2=2, dp[2]의 경우에 dp[2]를 곱해준다.
dp[4] = dp[2] x dp[2] + 2
그리고 특수한 바리에이션 2를 더해준다.

다음은 dp[6]의 경우를 보자. dp[6] = dp[4]*dp[2]… 그리고 dp[4]의 특별한 바리에이션 2개 곱하기 dp[4-2] 를 해줘야한다.
그리고 +dp[6]만의 특별한 형태 2개 를 더해준다. => dp[6] = dp[4] x dp[2] + dp[2] x 2 + 2
어느정도 형태가 보인다.
dp[8]의 경우도 같다.
dp[8] = dp[6] x dp[2] + dp[4] x 2 + dp[2] x 2 + 2
의 형태가 나온다.

왜 첫 dp[n-2]만 dp[2]를 곱해줄까?
그건 위에서도 말 했듯이(뭘?), 만약 dp[8]의 경우에서 dp[4] x dp[8-4]를 하려고 했다면 무수한 중복이 일어났을 것이다.
무슨 중복이냐, 그건 dp[6] x dp[2]에서 이미 나온 경우의 수일 것이다.
그럼 dp[4] x 2에서 2는 무었일까.
바로 저 위의 독특한 형태가 2가지여서 2를 곱해준것이다.
dp[4]일 경우에는 3x4칸의 독특한 형태 2가지,
dp[2]일 경우에는 3x6칸의 독특한 형태 2가지,
그리고 마지막으로 dp[8]자체의 3x8칸의 독특한 형태 2가지 식으로 말이다.

나는 맨처음에 dp[8] = dp[6] x dp[2] + dp[4] x dp[4] + dp[2] x dp[6] 식이 왜 안되는지 한참동안 직접 그리면서 헤맸다..

정답 코드

const readline = require('readline');
const rl = readline.createInterface({
  input: process.stdin,
  output: process.stdout
});
let input = [];
rl.on('line', function (line) {
  input.push(line)
})
  .on('close', async function () {
  // 답안 작성
  let answer = '';
  let n = input[0];
  answer = three_tile(n);
  
  console.log(answer)
  process.exit();
});

function three_tile(n){
  if(n%2==1)return 0;
  let arr = new Array(n*1+1).fill(0);
  arr[2] = 3;
  if(n==2)return arr[2];
  for(let i=3;i<=n;i++){
    if(i%2==0){
      arr[i] = arr[i-2]*3 + 2;
      k=i-2;      
      while(k>=2){        
        arr[i] = arr[i]+ arr[k-2]*2
        k -= 2;
      }
    } 
  }
  return arr[n]
}