본문으로 건너뛰기

790 - Domino and Tromino Tiling

info

풀이 키워드​

스포주의

DP 수학


풀이 코드​

info
  • 메모리: 41100 KB
  • 시간: 1 ms
class Solution {
    int n;
    final long mod = 1_000_000_007;
    int memo[][] = new int[2][1000];

    public int dp(int i, boolean gap) {
        if (i == n) return gap ? 0 : 1;
        if (i > n) return 0;
        if (memo[gap?1:0][i] != -1) return memo[gap?1:0][i];

        long res = 0L;
        if (gap) {
            res += dp(i+1, false); // ㄱ
            res += dp(i+1, true); // ㅡ
        }
        else {
            res += dp(i+1, false); // ㅣ
            res += dp(i+2, false); // =
            res += 2L * dp(i+2, true); // ㄴ
        }
        res %= mod;

        return memo[gap?1:0][i] = (int)res;
    }

    public int numTilings(int n) {
        this.n = n;
        Arrays.fill(memo[0], -1);
        Arrays.fill(memo[1], -1);

        return dp(0, false);
    }
}

풀이 해설​

문제 보자마자 어? 2×n 타일링 문제 아님? 했는데

비슷하긴 개뿔 ㄴ모양 ㄱ모양 타일이 추가된 업그레이드 버전이었음.

문제에선 도미노라고 하는데 그냥 타일이라고 하겠다.


📌 2×n 타일 문제의 특징​

타일링은 주로 빡구현이거나 DP에 해당한다. 이전에 DP로 푼 적 있어서 유형은 바로 알아챘다.

한가지 더 잡고 갈 포인트는 '2×n'이다. board가 2차원 배열이니 2중 for문 돌면서 빈 칸 찾으면 다음 dp 진행하는 방식을 떠올릴 수 있겠지만

사실은 그냥 테트리스 오른쪽으로 엎어놓은 것 마냥 딱 맞게 채워나가는 식의 단방향 dp이다.

그래서 백준 문제의 경우 메모이제이션도 1차원이고 dp 인자도 1개(x방향 인덱스)가 들어가지만...


📌 ㄴㄱ타일로 인한 차원 증가​

이 추가된 타일 모양 때문에 인자가 하나 더 추가되어 해당 문제는 인자 2개, 2차원 메모이제이션으로 처리해야 한다.

ㄴ 타일을 붙이면 위쪽에 공간이 생겨버리는데, 이 때문에 다음 호출된 dp에서 분기점이 생기기 때문이다.

물론, 공간이 안생기는 경우도 있다. ㅣ 모양 타일을 붙였거나, = 모양 타일을 붙였을 경우이다.

따라서 타일링 상태의 공간 유무를 추가된 gap 인자로 관리한다. true이면 빈 공간이 있다는 의미이다.


📌 base case​

if (i == n) return gap ? 0 : 1;
if (i > n) return 0;

i가 n인 경우와 n보다 큰 경우로 나뉜다.

  • n보다 크다는 것은 이전 호출에서 bound를 초과하여 타일링했다는 것이므로 n-1 -> n+1 로 진행한 case를 의미한다. 즉, 무효한 case이다.

  • n과 동일하다는 것은 bound에 맞게 타일링하긴 했는데 n-2 -> n 또는 n-1 -> n ㄴㄱ 타일 때문에 빈 공간이 있는 상태일 수 있으므로 return 문에 삼항연산자 분기가 추가된다.


📌 recursion​

long res = 0L;
if (gap) {
    res += dp(i+1, false); // ㄱ
    res += dp(i+1, true); // ㅡ
}
else {
    res += dp(i+1, false); // ㅣ
    res += dp(i+2, false); // =
    res += 2L * dp(i+2, true); // ㄴ
}
res %= mod;

요 부분은 심플하게 빈 공간 있냐 없냐고 구분해서 재귀하는 로직인데,

ㄴ 타일 진행값에 2가 곱해지는 이유는 사실 ㄴ도 가능하고 ┌ 도 되기 때문이다.

caution

mod는 합산된 상태에서 처리해야지, 2L * dp(i+2, true)에 mod해서 res에 합산한다거나 하는 식은 WA이다.


📌 수학적 접근법 (중요)​

점화식의 일반항 공식​

공식

처음에 공식이래서 O(1)O(1) 인줄 알았는데 점화식의 closed-form이었다.

따라서 아래 방식과 동일하다.

numTilings(n)=numTilings(n−1)×2+numTilings(n−3)numTilings(n) = numTilings(n−1) \times 2 + numTilings(n−3)

numTilings(1)=1numTilings(1) = 1
numTilings(2)=2numTilings(2) = 2
numTilings(3)=5numTilings(3) = 5

하지만 이걸 구현하는 방식에서 시간복잡도가 갈린다.

심플하게 상단의 3개 값만 하드코딩하고 for문 돌리면 O(n)O(n) 솔루션 완성~ 이고

matrix exponentiation으로 풀면 O(log n)O(log\,n) 풀이가 된다. (피보나치를 log N으로 연산하는 그 방식 맞다.)

관련 내용에 대한 USACO Guide

행렬 풀이
class Solution {
    static final int mod = 1000000007;

    private long[][] multiply(long[][] A, long[][] B) {
        long[][] C = new long[3][3];
        for (int i = 0; i < 3; i++) {
            for (int j = 0; j < 3; j++) {
                long sum = 0;
                for (int k = 0; k < 3; k++) {
                    sum = (sum + A[i][k] * B[k][j]) % mod;
                }
                C[i][j] = sum;
            }
        }
        return C;
    }

    private long[][] power(long[][] base, long exp) {
        long[][] result = {{1,0,0},{0,1,0},{0,0,1}};
        while (exp > 0) {
            if ((exp & 1) != 0) result = multiply(result, base);
            base = multiply(base, base);
            exp >>= 1;
        }
        return result;
    }

    public int numTilings(int n) {
        if (n == 0) return 1;
        if (n == 1) return 1;
        if (n == 2) return 2;
        long[][] t = {{2,0,1},{1,0,0},{0,1,0}};
        long[][] p = power(t, n - 2);
        long ans = (p[0][0]*2 + p[0][1]*1 + p[0][2]*1) % mod;
        return (int)ans;
    }
}

메모​

  • 자바도 digit separator가 있더라 ^.^ (현대 언어는 다 있다고 함)
  • 참고로 0ms는 for문으로 돌린 애들인데 TC 차이 안나도 수학적 원리는 아는 것이 좋다고 생각한다.
    • 코테는 for문 추천
  • 유익하므로 꼭 복습하기