[리트코드] 790. Domino and Tromino Tiling

https://leetcode.com/problems/domino-and-tromino-tiling/description/?envId=leetcode-75

문제 이해하는 데 꽤나 오래걸려서... 이해하면서 작성했던 것 정리해둔다.

 

문제

2칸짜리 도미노와 3칸짜리 도미노가 있을 때, 
2xn 짜리 보드판 전체를 도미노로 덮을 수 있는 모든 방법의 수를 \(10^9+7\)로 나눈 나머지를 구한다.

• 각 도미노는 회전하여 배치할 수 있다.
• 1 ≤ n ≤ 10^3

 

접근

행(row)는 2줄로 고정되어 있으므로 열(col)을 첫 번째부터 차례대로 이동하면서 가능한 경우에 따라 칸을 채운다.

4열짜리 보드판이 있다고 가정한다. 이 때 열을 하나씩 확인하면서 가능한 배치의 수를 생각해본다.

[현재 열의 2칸이 모두 비어있을 경우]

1. 세로 도미노 배치: 0열에 있는 모든 칸을 채울 수 있다.
2. 가로 도미노 배치: 0열에 있는 한 칸과 1열에 있는 한 칸을 채울 수 있다.
   이 때 보드판을 채우기 위해 그 아래에 놓을 수 있는 건 가로 도미노 밖에 없기 때문에 자동으로 아래에는 가로 도미노가 배치된다.
3. 트로미노 배치: 0열에 있는 모든 칸과 1열에 있는 한 칸을 채울 수 있다.
4. 트로미노 배치: 0열에 있는 모든 칸과 1열에 있는 한 칸을 채울 수 있다.

위와 같이 도미노를 배치한 뒤 빈 칸이 있는 다음 열로 이동해야 하는데 배치 방법에 따라 다음 열의 배치 상태가 달라지므로 이동할 열이 다르다.

1. 세로 도미노를 배치한 경우, 바로 다음 1열의 두 칸이 비어있으므로 1열로 이동한다.
2. 가로 도미노를 배치한 경우, 바로 다음 1열의 두 칸이 이미 모두 채워져 있으므로 다다음인 2열로 이동한다.
3. 트로미노를 배치한 경우, 바로 다음 1열의 한 칸이 비어있으므로 1열로 이동한다.
4. 트로미노를 배치한 경우, 바로 다음 1열의 한 칸이 비어있으므로 1열로 이동한다.

여기서 현재 위치한 열의 2칸이 모두 비어있다면 똑같은 배치 경우의 수를 고려하면 된다.
그러나 1칸만 비어있을 경우엔 새로운 배치 방법을 생각해야 한다.

 

[현재 열의 1칸만 비어있을 경우]

1. 가로 도미노 배치: 비어있던 1칸을 채워서 현재 열을 모두 채우지만, 동시에 다음 2열의 1칸만 채운다.
2. 트로미노 배치: 비어있던 1칸을 채워 현재 열을 모두 채움과 동시에 다음 2열의 2칸 모두 채운다.

도미노를 배치한 뒤 역시 빈 칸이 있는 다음 열로 이동하는데 배치 방법에 따라 다음 열의 배치 상태가 달라지므로 이동할 열이 다르다.

1. 가로 도미노 배치: 바로 다음 2열의 한 칸이 비어있으므로 2열로 이동한다.
2. 트로미노 배치: 바로 다음 2열의 두 칸 모두 채워져 있으므로 다다음 3열로 이동한다.

 

설계

위 접근 방식을 살펴보면 각 열마다 (1)빈 칸 유무 확인 후 (2)확인한 결과에 따라 가능한 경우로 배치를 반복한다. 그러므로 재귀를 활용한다.

//처음 열부터 끝 열까지 탐색한다.
	//기저 조건: 열 끝에 도착하면, 보드판 전체를 덮었는지 확인 후 카운트 - 종료
	//기저 조건: 배치한 도미노가 보드판 외로 삐져나갔다면 불가능한 상황이므로 카운트 X - 종료
	
	//현재 열의 2칸이 모두 비어있을 경우
		//1. 세로 도미노: i+1열로 이동
		//2. 가로 도미노: i+2열로 이동
		//3. 트로미노: i+1열로 이동
		
	//현재 열의 1칸만 비어있을 경우
		//1. 가로 도미노: i+1열로 이동
		//2. 트로미노: i+2열로 이동

재귀 함수이므로 기저 조건을 설정해준다. 

 

구현

`한 칸만 빈 상태`를 구분하기 위해 `boolean existHalf` 변수를 사용한다.

class Solution {
    final int MOD = 1000000007;

    public int numTilings(int n) {
        return (int)put(0, n, false); //현재 열, 열 길이, 빈 칸 존재     
    }

    long put(int col, int n, boolean existHalf) {
        //base case
        if(col == n) return existHalf ? 0 : 1; //열 테두리 도착 => 빈 칸 존재하는지 확인 
        if(col > n) return 0; //보드판 탈출

        //현재 열이 모두 비었으면 3가지 가능
        if(!existHalf) {
            //3가지 경우에서 가능한 경우의 수를 모두 더해서 리턴 
            //1. 세로로 도미노 하나 놓기 -> 다음 열로 이동 (빈 칸 없음)
            //2. 가로로 도미노 하나 놓기 -> 자동으로 밑에도 가로 도미노 배치 -> 다다음 열로 이동 (빈 칸 없음)
            //3. 트로미노 놓기 -> 현재 열은 꽉 채우고 다음 열에 빈 칸 발생 -> 다음 열로 이동 + 빈 칸 있음!!!
            return (put(col+1, n, false) + put(col+2, n, false) + put(col+1, n, true)) % MOD;
        }

        //현재 열에 반쪽짜리 도미노가 있다면 -- 전 열에서 놓은 트로미노 조각 -> 2가지 가능
        else {
            //2가지 경우에서 가능한 경우의 수를 모두 더해서 리턴 
            //1. 뒤집은 트로미노를 배치해서 맞물려 채우기 -> 다음 열도 채워짐 -> 다다음 열로 이동 (빈 칸 없음)
            //1-1. 이 경우 트로미노가 두 방향으로 놓여있을 수 있으므로 *2 
            //2. 가로 도미노 놓기 -> 현재 열은 채워지지만, 다음 열에 반쪽만 채워지면서 새로운 빈 칸 발생 -> 다음 열로 이동 + 빈 칸 있음!!!
            return (2L * put(col+2, n, false) + put(col+1, n, true)) % MOD;
        }
        
    }
    
}

 

그러나 위와 같이 작성할 경우, 시간 복잡도에서 문제의 조건을 만족하지 않아 시간 초과가 발생하면서 죽는다.
원인은 똑같은 값에 대해서도 계속해서 중복 연산을 수행하고 있기 때문이니까, 처음에 연산한 값을 저장해줄 배열을 사용한다. 이 배열을 사용해서 똑같은 값에 대해 연산을 요구할 경우, 배열에 이미 저장된 값인지 확인한 후 저장되어 있다면 즉시 그 값을 반환한다.

 

class Solution {
    final int MOD = 1000000007;
    Long[][] dp;

    public int numTilings(int n) {
        dp = new Long[n+1][2];
        return (int)put(0, n, 0); //현재 열, 전체 열 길이, 빈 칸 존재 유무
    }

    long put(int col, int n, int existHalf) {
        //열 모두 지났으면 확인 및 종료
        if(col == n) return (existHalf == 1) ? 0 : 1;
        //보드판 외 -> 종료 
        if(col > n) return 0;

        //dp에 이미 계산된 값이 있으면 계산하지 않음
        if(dp[col][existHalf] != null) return dp[col][existHalf];

        if(existEmpty == 1) return dp[col][existEmpty] = (put(col+1, n, 1) + (2L * put(col+2, n, 0))) % MOD;
        return dp[col][existHalf] = (put(col+1, n, 0) + put(col+2, n, 0) + put(col+1, n, 1)) % MOD;
    }
}