[프로그래머스] 아방가르드 타일링 - JAVA

이 문제를 풀이한 사람들을 보면
대부분이 규칙성을 찾고 점화식을 세우는 방식을 사용하고 있습니다.

컴퓨터 니가 해

이 문제를 봤을 때 하나의 위치에
총 6가지 타일링 방식이 있는데

$n$이 증가할수록 기하급수적으로 경우의 수가 많아지고
직접 모양들을 시뮬레이션 해보면서 경우의 수를 찾는 것이 어렵습니다.

저는 머리가 아픈 나머지 이 작업을 컴퓨터가 수행하도록 구현했습니다.
말하자면 니가 해 방식인거죠..

이전에 백준의 격자판 채우기 문제를 풀었던 적이 있습니다.

DP + 비트마스킹 + 토글링을 사용한다면
메모리도 터지지 않고 시간 내에도 문제를 해결할 수 있을 것입니다.

대충 계산해보면 $O(N*2^7)$인 것 같습니다.
그래서 이 방식으로 문제를 해결해 보겠습니다.

---

접근 방법

dp 선언

dp는 토글링을 해야 하고
또 현재 확인해야할 상태는 0번 ~ 6번 인덱스입니다.

그러므로 dp는 아래와 같이 생성했습니다.

int[][] dp = new int[2][1 << 7];

행은 크기 2로 dp의 before와 current를 토글링
열은 크기 $2^7$로 0~127까지
이진수로 표현하면 0000000 ~ 1111111까지 표현할 수 있습니다.

---

그래서 왜 1<<7인데?

우선 저는 $3 * n$ 문제를 $n * 3$ 문제로 바꿔서 풀었습니다.
저한테는 이 방식이 더 직관적이고
논리적으로 같은 결과를 도출하기 때문입니다.

그래서 $n$이 6이라고 가정을 할 때
0번 인덱스에서 타일을 놓을 수 있는 방법은 총 6가지 입니다.
(빨간색으로 묶은 부분은 하나입니다)

여기서 타일을 놓을 때
6번 인덱스, 즉 7번째 위치에 타일을 놓는 경우가 최대이기 떄문에
상태를 1<<7까지 기억하는 것입니다.

그래서 이전까지 놓았던 상태를 before
현재 새로운 타일을 추가하기 위한 current
이 두가지로 토글링해나가는 것입니다.

---

점화식

따로 점화식 수식은 없습니다.
모두가 아래와 같은 동일한 흐름을 가지고 있습니다.

int check = 현재 타일의 칸 위치
if (인바운드 체킹 && (state & check) == 0) {
	int nextState = (state | check) >> 1; 
	dp[current][nextState] = (dp[current][nextState] + dp[before][state]) % MOD;
}

현재 확인하는 타일을 놓을 수 있는지 확인하기 위해
타일을 놓기 위해 필요한 칸을 마스킹화 한 것이 check 변수 입니다.

이 check로 현재 state를 검증하고 또 inbound인지 체킹한 후에
놓을 수 있다고 판단되면 nextState에 경우의 수를 반영하는 것입니다.

---

코드

코드가 풀고난 후에 바로 블로그 포스팅을 하느라
더티 코드이지만
6가지 check에 대해 static 배열로 관리하고
for 문으로 하나의 점화식을 사용한다면 더 깔끔한 코드가 될 것 같습니다.

class Solution {
    static final int MOD = 1000000007;

    public int solution(int n) {
        int totalCells = n * 3;
        int[][] dp = new int[2][1 << 7];
        
        dp[0][0] = 1;
        
        int before = 0;
        int current = 1;
        int inbound = totalCells;

        for (int index = 0; index < inbound; index++) {
            // current 배열 초기화
            for (int i = 0; i < (1 << 7); i++) dp[current][i] = 0;

            for (int state = 0; state < (1 << 7); state++) {
                if (dp[before][state] == 0) continue;

                if ((state & 1) != 0) {
                    int nextState = state >> 1;
                    dp[current][nextState] = (dp[current][nextState] + dp[before][state]) % MOD;
                    continue;
                }

                // 1. 역 ㄴ (왼쪽으로 튀어나오는 _| 모양) -> c가 0보다 커야 함
                int check = (1 << 0) | (1 << 2) | (1 << 3);
                if (index + 3 < inbound && index % 3 > 0 && (state & check) == 0) {
                    int nextState = (state | check) >> 1;
                    dp[current][nextState] = (dp[current][nextState] + dp[before][state]) % MOD;
                }

                // 2. 가로 ㅡ (1x3) -> 무조건 c=0 에서 시작해야 함
                check = (1 << 0) | (1 << 1) | (1 << 2);
                if (index % 3 == 0 && (state & check) == 0) {
                    int nextState = (state | check) >> 1;
                    dp[current][nextState] = (dp[current][nextState] + dp[before][state]) % MOD;
                }

                // 3. 세로 ㅣ (3x1)
                check = (1 << 0) | (1 << 3) | (1 << 6);
                if (index + 6 < inbound && (state & check) == 0) {
                    int nextState = (state | check) >> 1;
                    dp[current][nextState] = (dp[current][nextState] + dp[before][state]) % MOD;
                }

                // 4. 역ㄱ (오른쪽 1칸짜리 빈 공간 있는 ㄱ모양) -> c가 0, 1이어야 함
                check = (1 << 0) | (1 << 1) | (1 << 3);
                if (index + 3 < inbound && index % 3 < 2 && (state & check) == 0) {
                    int nextState = (state | check) >> 1;
                    dp[current][nextState] = (dp[current][nextState] + dp[before][state]) % MOD;
                }

                // 5. ㄱ (오른쪽으로 뻗는 기본 ㄱ모양) -> c가 0, 1이어야 함
                check = (1 << 0) | (1 << 1) | (1 << 4);
                if (index + 4 < inbound && index % 3 < 2 && (state & check) == 0) {
                    int nextState = (state | check) >> 1;
                    dp[current][nextState] = (dp[current][nextState] + dp[before][state]) % MOD;
                }

                // 6. ㄴ (오른쪽으로 튀어나오는 L 모양) -> c가 0, 1이어야 함
                check = (1 << 0) | (1 << 3) | (1 << 4);
                if (index + 4 < inbound && index % 3 < 2 && (state & check) == 0) {
                    int nextState = (state | check) >> 1;
                    dp[current][nextState] = (dp[current][nextState] + dp[before][state]) % MOD;
                }
            }
            before ^= 1;
            current ^= 1;
        }

        return dp[before][0];
    }
}