[백준 2133 : JAVA] 타일 채우기 / DP

문제

---

[그림 1] 문제

 

 

 

풀이

---

먼저 N이 홀수일 경우는 타일로 완전히 채울 수 없다. 타일은 2의 배수인데, N이 홀수가 되어버리면 벽의 넓이가 홀수가 되기 때문이다.

즉, 타일로 벽을 가득 채우기 위해선 벽의 넓이가 2의 배수가 되어야하는데, N이 홀수면 벽의 넓이가 홀수가 되어버리기 때문이다.

따라서 첫 시작은 N이 2인 경우부터이다.

 

[그림 2] N=2일 경우 채울 수 있는 타일의 경우의 수

 

다음 짝수인 N=4인 경우를 생각해보자.

3*4 = 3*2 + 3*2    // N=2인 경우를 두 번 합한 것으로 생각해볼 수 있다.

 

그럼 N=2일때 3가지 경우의 수를 가졌으니, N=4는 3*3=9가지 경우의 수를 가질까?

 

[그림 3] N=4일 경우 추가된 예외 케이스

 

3*2로는 만들 수 없었지만, 3*4로는 만들 수 있는 추가적인 경우의 수가 2개 존재한다. 따라서, N=4는 11가지가 된다.

참고로, 예외 케이스에 대해선 노가다로 찾는다. (다른 방법이 있다면 댓글 달아주세요..!)

 

N=6 인 경우를 보자.

 

[그림 4] N=6일 경우 나눠볼 수 있는 모양

 

위 그림에서 보는 것처럼 3*6은 3가지 경우로 풀어서 생각해볼 수 있다.

1. 3*6 = 3*2 + 3*2 + 3*2 = 3 * 3 * 3 = 27 가지
2. 3*6 = 3*4 + 3*2 = 11 * 3 = 33 가지
3. 3*6 = 3*2 + 3*4 = 3 * 11 = 33 가지 

 

그런데, 잘 생각해보면 위의 2, 3번째 케이스의 경우의 수에는 1번째 케이스의 경우의 수도 포함되어 있다.

2, 3번째 케이스의 경우의 수 중에 1번째 케이스의 경우의 수에 포함되지 않는 것은 3*4가 가지는 예외 케이스 2가지에 대해서다.

즉, DP[6] = DP[4] * DP[2] + DP[2] * 2 (2는 예외 케이스)  라는 점화식이 도출되었다. 그런데, 여기서 끝이 아니다. N=4일 경우와 같은 맥락으로 N=6일 경우에 대해서만 만들 수 있는 예외 케이스가 2가지 존재한다. (N=4일 때와 마찬가지로, 가로로 연결시키는 경우)

 

따라서, 최종적으로 도출되는 식은 DP[6] = DP[4] * DP[2] + DP[2] * 2 + 2 가 된다.

 

N=8일 경우도 마찬가지로

DP[8] = DP[6] * DP[2] + DP[4] * 2 + DP[2] * 2 + 2 가 된다.

 

N=1부터 시작하지만, 점화식의 규칙을 맞춰주기 위해 마지막 부분에 DP[0]=1 이라 정해두고, 추가해보자.

DP[N] = DP[N - 2] * DP[2] + DP[N - 4] * 2 + DP[N - 6] * 2 + DP[N - 8] * 2 라는 점화식을 도출해낼 수 있다.

 

 

 

코드

---

import java.io.*;

public class Main {

    private static int N;
    private static int[] cache;

    public static void main(String[] args) throws Exception {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        N = Integer.parseInt(br.readLine());

        // 채우려는 타일의 크기가 2의 배수이므로, N이 짝수 크기인 경우만 완전히 채울 수 있다.
        cache = new int[N + 1];
        if (N % 2 == 0) {
            cache[0] = 1;
            cache[2] = 3;
            for (int i = 4; i <= N; i += 2) {
                cache[i] = cache[i - 2] * cache[2];

                for (int j = i - 4; j >= 0; j -= 2) {
                    cache[i] += (cache[j] * 2);
                }
            }
        }

        System.out.println(N % 2 == 0 ? cache[N] : 0);
    }
}