[programmers/js] 3 x n 타일링

3 x n 타일링

https://school.programmers.co.kr/learn/courses/30/lessons/12902

문제 설명

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

1. 타일을 가로로 배치 하는 경우
2. 타일을 세로로 배치 하는 경우

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

풀이

3×n 문제는 짝수 길이(n이 짝수)일 때만 타일링이 가능합니다.
n이 홀수일 경우는 반드시 빈 공간이 남을 수밖에 없기 때문입니다.

n=2
총 3가지 패턴이 존재 합니다.

[1 1]   [1 2]   [1 1]
[2 2]   [1 2]   [2 3]
[3 3]   [3 3]   [2 3]

n=3
3×3 벽은 절대 채울 수 없습니다.
홀수이기 때문에 빈 칸이 남음 → dp[3] = 0

n=4
기존 타일 2개를 이어붙인 조합으로 dp[2] * dp[2] = 3 * 3 = 9 경우를 가집니다. 이때, n=4에서만 가능한 유니크한 패턴 2개 존재해 최종 dp[4] = 3×3 + 2 = 11개의 경우가 존재합니다.

n=6
1. 기존 조합 확장 dp[4] * dp[2] = 11 * 3 = 33
2. n=4 유니크 패턴 양 옆에 dp[2]를 붙이는 경우 → 3 * 2 = 6
3. n=6 전용 유니크 패턴 → 2개 추가

최종 33 + 6 + 2로 41개의 경우가 존재

function solution(n) {
    const r = 1_000_000_007;
    if (n % 2) return 0;
    
    const dp = Array(n).fill(0);
    dp[2] = 3;
    
    for (let i = 4; i <= n; i += 2) {
        dp[i] = dp[i - 2] * dp[2] + 2;
        
        for (let j = i - 4; j >= 0; j -= 2) {
            dp[i] += dp[j] * 2;
        }
        dp[i] %= r;
    }
    
    return dp[n]
}