**백준 2133번 타일 채우기(자바) - DP

타일 채우기

한국어   

시간 제한메모리 제한제출정답맞은 사람정답 비율

2 초

128 MB

30948

10873

8552

35.206%

문제

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

입력

첫째 줄에 N(1 ≤ N ≤ 30)이 주어진다.

출력

첫째 줄에 경우의 수를 출력한다.

예제 입력 1 복사

2

예제 출력 1 복사

3

힌트

아래 그림은 3×12 벽을 타일로 채운 예시이다.

---

이 문제가 지금까지 푼 것 중에 가장 어려웠던 것 같다.

이 문제의 핵심은 특수 케이스를 생각하는 것이다.

예를 들어 3X8 크기의 벽이 있다면

3X2 와 3X6으로 나누는 경우(DP[6]*DP[2]) + 3X4의 특수경우와 3X4로 나누는 경우 (DP[N-4] * 2) + 3X6의 특수 경우와 3X2로 나누는 경우(DP[N-6] * 2) + 3X8에서 나오는 특수경우(DP[0] * 2) 로 구할 수 있다.

 

N >= 4일 때만 특수 경우가 나오게 되고, 각 N에서 특수 경우는 모두 2개씩이다.

따라서 점화식을 구해보면 

DP[N] = DP[N-2]*DP[2] + DP[N-4] * 2(특수 경우의 개수가 2이므로) + DP[N-6] * 2 + DP[N-8] * 2 + ... + DP[0] * 2이다.

(이때 DP[0]에는 1을 저장해놓는다.)

 

<Top-down>

import java.util.Scanner;

public class Main {
    static int[] dp;
    public  static void main(String args[]) {
        Scanner scanner = new Scanner(System.in);
        int n = scanner.nextInt();
        dp = new int[n+1];
        dp[0] = 1;
        if (n > 1 && n % 2 == 0) {
            dp[2] = 3;
            result(n);
        }
        System.out.println(dp[n]);
    }

    public static int result(int n) {
        if (dp[n] > 0) return dp[n];
        else if (n >= 4){
            dp[n] = result(n-2) * dp[2];
            for (int j = 4; j <= n; j+=2) {
                dp[n] += result(n-j) * 2;
            }
        }
        return dp[n];
    }
}

 

참고 블로그

[알고리즘 문제] 백준2133 - 타일 채우기 (tistory.com)