[백준 1648]격자판 채우기 - JAVA

접근 방법

이 문제는 2x1 도미노를 놓아 격자판을 모두 채우는 경우의 수를 세는 문제입니다.
그러면 가장 먼저 해야할 것은 도미노의 형태입니다.
가로와 세로로 놓을 수 있습니다.

두 번째로 해야할 것은 경우의 수를 어떻게 메모이제이션할까 입니다.
대부분의 가짓수 문제들은 Dynamic Programming 문제일 확률이 높습니다.

그 점을 고려해서 우선 시간 복잡도와 공간 복잡도 등을 확인해 DP 로 풀 수 있는지 파악했습니다.
격자판을 그리는데는 $14 * 14 = 196$ 이 최대이기 때문에 충분했고
이 모든 격자 그래프 위치에 대해 모든 상태를 저장하려면 최대 $2^{196}$이기 때문에 절대 이 문제를 단순한 2차원 DP 로는 풀 수 없는 문제라는 것을 파악했습니다.

그래서 아래와 같은 생각을 했습니다.

이 문제에서는 특정 위치 index 에서 특정 상태 state 에 따라
다음 index+1 위치의 new_state 에 경우의 수를 누적하는 로직을 가지고 있습니다.

특정 index 의 특정 state 에 따라
현재 위치에서 가로 또는 세로로 넣은 도미노의 상태를 가진 경우의 수를 index+1 에 누적하기 때문에 index+1이 필요로하는 state의 범위는 분홍색과 같은 범위이며 그 길이가 $M$인 상태를 기억해야 합니다.

즉 state 는 $2^M$ 개의 상태만 기억하면 된다는 것이고
기본적인 $dp$ 배열은 다음과 같은 크기로 선언합니다. ($dp[N*M][1<<M]$)

다음은 일반적인 $dp$ 연산과 동일합니다.
index (격자 그래프의 좌표를 1차원화)와 state를 순회하면서
블록을 넣거나 이미 넣어진 상태면 경우의 수만 넘기는 로직을 수행하면 됩니다.
현재 index 와 state 에 따라 로직을 수행하는데 내용은 다음과 같습니다.

• 현재 위치에 경우의 수가 없는 경우 -> 생략 (dp[index][state] == 0 )
• 현재 위치에 이미 블록이 놓아진 상태인 경우 -> 현재 경우의 수만 다음 index로 넘기기
  • 이 때 다음 위치에서는 다음 좌표에 대한 14개의 상태를 표현하기 때문에 state 슬라이딩
  • dp[index+1][state>>1] = dp[index+1][state>>1] + dp[index][state]
• 현재 위치에 블록을 놓을 수 있는 경우 -> 가로, 또는 세로의 상태를 보고 가능한 경우 블록 놓기
  • 가로 : 인바운드 체킹 + 오른쪽이 비어있는 상태 체킹
    • if ((index % M != M-1) && (state & 2) == 0)
  • 세로 : 인바운드 체킹
    • if (index + M < M * N)
• 마지막 위치에서 최종 경우의 수 출력

위의 로직을 수행할 때 항상 % 9901 연산을 해야하는 것을 잊으시면 안됩니다!!

코드

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.StringTokenizer;

public class Main {
    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        StringTokenizer st = new StringTokenizer(br.readLine());

        int N = Integer.parseInt(st.nextToken());
        int M = Integer.parseInt(st.nextToken());

        int[][] dp = new int[N*M][1<<M];
        dp[0][0] = 1;

        for (int index = 0; index < N*M-1; index++) {
            for (int state = 0; state < 1 << M; state++) {
                if (dp[index][state] == 0) continue;
                if ((state & 1) == 1) {
                    dp[index+1][state>>1] = (dp[index+1][state>>1] + dp[index][state]) % 9901;
                }
                else {
                    if ((index % M != M-1) && (state & 2) == 0) {
                        dp[index+1][(state>>1)|1] = (dp[index+1][(state>>1)|1] + dp[index][state]) % 9901;
                    }

                    if (index+M < M*N) {
                        dp[index+1][(state>>1)|(1<<(M-1))] = (dp[index][state] + dp[index+1][(state>>1)|(1<<(M-1))]) % 9901;
                    }
                }
            }
        }
        System.out.println(dp[N*M-1][1]);
    }
}

추가 최적화

이 문제를 풀면서 생각난 것은 참조하는 것은 이전 index 와 현재 index 밖에 없는데 굳이 모든 격자 좌표를 배열로 만들 필요가 있을까? 에서 발생한 방안입니다.

$dp$에서 다루는 기본적인 공간 복잡도 최적화 방법이기도 한데 조금만 고민하신다면 상당한 메모리 효율을 향상시킬 수 있습니다! 여러분들도 도전해보세요 :)