[백준(baekjoon) 2133] 타일 채우기

문제

백준 2133

3×N 크기의 벽을 2×1, 1×2 크기의 타일로 채우는 경우의 수를 구해보자.

• N(1 ≤ N ≤ 30)

해결

알고리즘

DP로 풀었고, bottom-up 방식이랑 top-down 방식으로 각각 풀었다.

DP에 대해 아직 잘 모른다면 여기의 알고리즘 부분을 보자.

방법

자세한 설명을 뒤로 하고, 간단하게 핵심만 우선 정리하겠다.

1. N이 홀수일 때 경우의 수는 0이다.
2. width = 2씩 묶어 확인한다.
3. 3 X 2는 3가지 케이스가 나온다. 즉, dp[2] = 3이다.
4. 3 X 2n(n > 1)을 만족하는 케이스는 다음과 같이 나뉜다.
   
   1. 이전에 나오지 않은 특수 케이스 2가지.
   2. 3 X 2m(m = 1...n - 1)의 1번 특수 케이스와 dp[2n - 2m]이 합해진 케이스.
      
      • 이 경우 특수케이스는 3 X 2일 경우 3이고, 그 이상의 경우 2이다.
      • 위의 값과 dp[2n - 2m]을 곱해준다.
5. 4-1, 4-2번의 경우를 모두 더한 값이 dp[2n]이다.

왜 그럴까?

1. 짝수

우선, 채우려는 타일의 크기가 2의 배수이므로 N이 짝수일 경우에만 채울 수 있다.
즉, N이 홀수일 때 경우의 수는 0이다.

그리고 이를 통해 벽을 채울 수 있는 경우의 수는 width = 2씩 묶어 확인해야한다.라는 것을 알 수 있었다.

2. 디폴트 dp[2]

그럼, 짝수의 가장 최소 크기의 벽인 3 X 2를 살펴보자!

다음과 같이 3개의 경우의 수가 나온다는 것을 알 수 있다.
이후 나오는 벽의 가로 길이는 2의 배수이므로 이를 dp[2]에 저장해두고 활용할 수 있을 것 같다.

3. 예시를 통해 규칙 찾기

3 X 4의 경우를 통해 확인해보자.

1. 오른쪽 처럼 3 X 2 두개를 이어 붙여 만들 수 있었다.
   dp[2] = 3이므로 3 * 3 = 9의 경우의 수가 나온다.
2. 그리고 왼쪽 처럼 특수 케이스 2개가 나왔다.

이렇게 dp[4] = 11이 나온다.

4. 특수 케이스..?!

위에서 확인한 특수 케이스는 가운데 부분을 2 X 1로 채우고, 양 사이드를 1 X 2로 채운 후 아래 혹은 위로 2 X 1로 모두 채우는 방식이다.
이러한 규칙은 3 X 2n(n > 1)을 만족하는 모든 벽에 적용 가능하다!

따라서 가로 길이가 2이상인 경우 항상 2개의 특수 케이스가 나타난다.
그럼 특수 케이스는 어떻게 처리해야 할까..?

5. 특수 케이스 + dp

각 크기의 벽을 작은 크기의 벽으로 나누어 정리한 결과,
3 X 2m(m = 1...n - 1)의 특수케이스와 dp[n - 2m]을 조합해서 문제를 해결하였다!
그리고 특수 케이스 2개를 추가해주었다.

쉽게 예시를 통해 확인하자.

특수 케이스인 벽은 []로 나타내겠다.

1. 3 X 2 + 3 X 4 = 3 * 11 = 33
   
   • 3 X 2는 특수 케이스가 없으므로 dp[2] = 3을 활용한다.
   • 3 X 4 : 이전에 구한 dp[4]를 가져온다.
   • 이 조합을 더 자세히 나누면 아래와 같다.
     
     • 3 X 2 + 3 X 2 + 3 X 2
     • 3 X 2 + [3 X 4]
2. [3 X 4] + 3 X 2 = 2 * 3 = 6
   
   • 위에서 [3 X 4]가 뒤쪽에만 사용되었다. 즉, 앞에서도 사용하자!
3. [3 X 6] = 2
   
   • 새로운 특수 케이스 등장!

dp[6]는 모든 케이스를 더한 33 + 6 + 2 = 41이다.
이와 같은 방식을 반복해서 최종적으로 문제를 해결할 수 있다.

구현 java

해당 코드는 쉬운 접근을 위해 dp를 n + 1의 크기만큼 생성한 것이다.

하지만 짝수만 구하면 되므로 불필요한 홀수자리를 없애 메모리를 줄인 방식도 구현했으나,
생각보다 결과 차이가 많이 나지 않아 그냥 접근성이 쉬운 코드만 올리겠다.

1. Bottom-Up 방식

1.import java.util.*;
2.
3.public class Main {
4.    static int[] dp;
5.    public static void main(String[] args) {
6.        Scanner sc = new Scanner(System.in);
7.        int n = sc.nextInt();
8.        dp = new int[n + 1];
9.
10.        int answer = 0;
11.        if (n % 2 == 0) {
12.            dp[2] = 3;
13.            dp[0] = 1;
14.            for (int i = 4; i <= n; i += 2) {
15.                for (int j = 2; j <= i; j += 2) {
16.                    int standard = j == 2 ? 3 : 2;
17.                    dp[i] += standard * dp[i - j];
18.                }
19.            }
20.            answer = dp[n];
21.        }
22.
23.        System.out.println(answer);
24.    }
25.}

2. Top-Down 방식

1.import java.util.*;
2.
3.public class Main {
4.    static int[] dp;
5.    public static void main(String[] args) {
6.        Scanner sc = new Scanner(System.in);
7.        int n = sc.nextInt();
8.        dp = new int[n + 1];
9.        System.out.println(n % 2 == 0 ? goTo(n) : 0);
10.    }
11.
12.    static int goTo (int n) {
13.        if (n == 0) return 1;
14.        if (n == 2) dp[2] = 3;
15.        else if (dp[n] == 0) {
16.            for (int i = 2; i <= n; i += 2) {
17.                int standard = i == 2 ? 3 : 2;
18.                dp[n] += standard * goTo(n - i);
19.            }
20.        }
21.        return dp[n];
22.    }
23.}

결과

1. Top-Down 메모리 줄인 방식
2. Bottom-Up 메모리 줄인 방식
3. Bottom-Up 방식
4. Top-Down 방식