문제설명

가로 길이가 2이고 세로의 길이가 1인 직사각형 모양의 타일이 있습니다. 이 직사각형 타일을 이용하여 세로의 길이가 3이고 가로의 길이가 n인 바닥을 가득 채우려고 합니다. 타일을 채울 때는 다음과 같이 2가지 방법이 있습니다

• 타일을 가로로 배치 하는 경우
• 타일을 세로로 배치 하는 경우

예를들어서 n이 8인 직사각형은 다음과 같이 채울 수 있습니다.

직사각형의 가로의 길이 n이 매개변수로 주어질 때, 이 직사각형을 채우는 방법의 수를 return 하는 solution 함수를 완성해주세요.

제한사항

• 가로의 길이 n은 5,000이하의 자연수 입니다.
• 경우의 수가 많아 질 수 있으므로, 경우의 수를 1,000,000,007으로 나눈 나머지를 return해주세요.

입출력 예

n	result
4	11

입출력 예 설명

입출력 예 #1
다음과 같이 11가지 방법이 있다.

출처: 프로그래머스 코딩 테스트 연습, https://programmers.co.kr/learn/challenges

설계 과정

점화식 계산을 설계를 먼저해야한다.
규칙을 찾아보면 다음과 같다.
n = 2 일 때 3가지,
n = 4 일 때 11가지,
n = 6 일 때 41가지,
n = 8 일 때 153가지
-> 점화식
f(i) = f(i) * 4 - f(i)
위를 구할때 n이 2씩 뛰어질때마다 새로운 케이스가 2개씩 추가 된다. 이를 고려하여 케이스르 구해보면 위와 같다. 이를 통해 점화식을 구하고, 이 점화식을 바탕으로 코드 구현

정답 코드

function solution(n) {
  const MOD = 1000000007;
  var dp = [0,3,11];
    if(n%2===1){
        return 0;
    }
    else{
        n = n/2;
    }
    
    for(var i =3;i<=n;i++){
        dp[i] = ((dp[i-1] * 4 % MOD) - (dp[i-2] % MOD) + MOD) % MOD;
    }
  return dp[n];
}

결과

이 문제는 코드 구현 자체는 어렵지 않지만 규칙을 찾고 점화식을 구하는데 애를 먹었다. 처음에 구현한 점화식은 당연히도 틀렸었다.

기존 2*N 타일링 문제는 추가 케이스가 없어서 쉽지만, 이 문제는 이 추가 케이스를 고려하는 것 때문에 까다롭다.