[JS] 3 x n 타일링

문제

프로그래머스

 

 

풀이

이 문제는 DP 알고리즘을 이용해 풀이하는 문제이다. 이 문제를 보면 홀수 길이의 경우 절대 조건을 만족하는 경우가 없기에 0을 반환한다.

 

짝수 길이의 경우 점화식이 존재한다. 처음에는 어떻게 점화식을 만들지 잘 몰랐다. 하지만, 조금 더 생각해보면 짝수 길이만 되며, 이전의 경우를 이용한 경우를 추가하며 이전 값들을 이용하는 DP 알고리즘의 이용이 필요하다는 것을 알게되었다.

 

점화식은 ((dp[i - 1] * 4)) - (dp[i - 2]) % 1000000007 이지만, 이 경우는 dp[i - 1] * 4의 값이 dp[i - 2]보다 작을 수 있기 때문에 음수가 나올 수 있다. 이러한 경우를 해결하기 위해 ((dp[i - 1] * 4) - (dp[i - 2]) + 1000000007) % 1000000007 이러한 식을 이용해야 한다.

 

코드

function solution(n) {
  if (n % 2 === 1) return 0;

  const dp = [0, 3, 11];

  for (let i = 3; i <= (n / 2); i++) {
    dp[i] = (((dp[i - 1] * 4)) - (dp[i - 2]) + 1000000007) % 1000000007;
  }

  return dp[n / 2];
}