[골드 4] 2133번 타일 채우기 ⭐️

문제 설명

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

입력

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

출력

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

풀이

• dp[n]은 dp[n-2]번째에 n=2 인 경우를 붙이면 된다.
• 이때 n=2일 때 개수가 3이므로 dp[n] = dp[n-2] * 3이다.
• 그러나 n=4일 때, n=2로 만들 수 없는 특수한 패턴이 2개 나타나므로 이를 더해주기 위해 dp[i] += dp[i-j] * 2를 해준다.

let N = require('fs').readFileSync('ex.txt').toString();
N = +N;

// 홀수면 불가능, return 안하면 밑에 콘솔이랑 중복되서 꼭 return 해줘야 함
if (N % 2) return console.log(0);

const dp = new Array(N + 1).fill(0);
dp[0] = 1;
dp[2] = 3;

for (let i = 4; i <= +N; i += 2) {
  dp[i] = dp[i - 2] * 3;

  for (let j = 4; j <= i; j += 2) {
    dp[i] += dp[i - j] * 2; // 예외 케이스
  }
}

console.log(dp[N]);

https://webruden.tistory.com/1048