790 - Domino and Tromino Tiling

info

문제 보기: 790 - Domino and Tromino Tiling
소요 시간: 💥1시간 4분
풀이 언어: java
체감 난이도: 3️⃣
리뷰 횟수: ✅

풀이 키워드

스포주의

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)$ 인줄 알았는데 점화식의 closed-form이었다.

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

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

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

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

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

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

메모

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

풀이 키워드​

풀이 코드​

풀이 해설​

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

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

📌 base case​

📌 recursion​

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

점화식의 일반항 공식​

메모​