[LeetCode] 790. Domino and Tromino Tiling

2×n 보드를 2×1 도미노와 L자 트로미노로 채우는 경우의 수. 답은 10^9+7로 나눈 나머지.

접근: 오른쪽 끝 덩어리로 경우 나누기

보드의 오른쪽 끝을 마무리하는 "더 이상 세로로 쪼갤 수 없는 덩어리"는 아래 중 하나다. 덩어리 길이가 k면 왼쪽에 2×(n-k) 보드가 남고, 그걸 채우는 방법은 f(n-k)가지다.

• 길이 1: 세로 도미노 1개. 1가지
• 길이 2: 가로 도미노 2개를 위아래로. 1가지
• 길이 3: 트로미노 2개가 맞물린 2×3 블록. 2가지
• 길이 4 이상: 트로미노 2개 사이에 가로 도미노를 끼운 블록. 각 2가지

길이 1, 2는 위아래로 뒤집어도 같은 모양이라 1가지. 길이 3부터는 트로미노가 L자라 위아래 비대칭이고, 뒤집으면 다른 타일링이 되어 2가지다.

f(n) = f(n-1) + f(n-2) + 2·f(n-3) + 2·f(n-4) + 2·f(n-5) + ...

꼬리 없애기

f(n)과 f(n-1)을 펼쳐 나란히 놓으면 뒷부분이 같다.

f(n)   = f(n-1) + f(n-2) + 2·f(n-3) + 2·f(n-4) + ...
f(n-1) =          f(n-2) + 1·f(n-3) + 2·f(n-4) + ...

빼면 꼬리가 전부 상쇄된다.

f(n) - f(n-1) = f(n-1) + f(n-3)
f(n) = 2·f(n-1) + f(n-3)

코드

function numTilings(n: number): number {
    const MODULO = Math.pow(10, 9) + 7
    const dp = [1, 1, 2]
    for(let i = 3; i <= n; i++) {
        dp[i] = (2 * dp[i - 1] + dp[i - 3]) % MODULO
    }
    return dp[n]
};

시작값 dp[0]=1(빈 보드는 아무것도 안 놓는 1가지), dp[1]=1, dp[2]=2.

f(3) = 2·2 + 1 = 5
f(4) = 2·5 + 1 = 11

시간 O(n), 공간 O(n).