[백준 *Java] - 타일 채우기 (2133)

 

 

타일 채우기

2133번: 타일 채우기

문제 설명
3 X N 크기의 벽을 2x1, 1x2 크기의 타일로 채우는 경우의 수를 구해보자.

입력
첫째 줄에 N(1 <= N <= 30)이 주어진다.

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

 

응..?

문제가 이렇게 간단하다고..?

문제는 간단하지만 정답률이 굉장히 저조한 문제입니다.

---

👇 접근방식

홀수로는 만들 수 없고, 짝수가 늘어날수록, 경우의 수가 더 많아지는 건 알겠는데, 그 예외를 무엇인지를 정의해서 점화식으로 만드는 게 어려워서 다른 분 코드를 보면서 이해를 했습니다:(

---

제가 이해한 바탕으로 설명을 하겠습니다.

점화식을 짜기 위해서 규칙이 있습니다

 

1. N은 홀수가 될수 없습니다.

홀수는 경우의 수가 0입니다. 고로, 홀수를 제외한 짝수만 구해주면 됩니다.

2. 예외의 상황이 있습니다. 그 점을 고려해서 점화식을 짜야합니다.

어떤 상황이냐면,

예를들어 N이 4일 때, 타일(3x2)가 두 개가 붙어있는 상태인데,

그 때 경우의 수가 타일(3x2)의 경우의 수는 3이니, 3 곱하기 3으로 총 9개인데, 정답이 9가 아니라 11입니다.

왜냐하면, 예외의 상황으로 만들 수 있는 경우의 수가 2개가 더 있습니다.

ㅗ	ㅗ	ㅁ	ㅁ
ㅅ	O	O	X
ㅅ	O	O	X

X	ㅎ	ㅎ	ㅂ
X	ㅎ	ㅎ	ㅂ
ㅅ	ㅅ	ㅇ	ㅇ

이렇게 타일(3x2) 두 개가 겹쳤을 때 추가로 나오는 경우의 수가 2개가 존재합니다.

여기서 이 예외를 포함시켜서 점화식을 만들어야합니다.

 

---

👇  하나씩 N을 따져가면서 확인해보겠습니다.

 

N이 2 일때,

• 타일(3x2) 1개  --> 3개

-> 그려보면 3개가 나옵니다. 따라서, DP[2]=3 입니다. 미리 초기화를 시킬 수 있습니다.

 

N이 4 일 때,

• 타일(3x2) 2개  --> 3 * 3 = 9개
• 타일(3x4) 1개  --> 특수 케이스 2개

-> 11개

 

N이 6 일 때,

• 타일(3x2) 3개  --> 3 * 3 * 3 = 27개
• 타일(3x4) 1개 + 타일(3x2) 1개 -->  특수케이스2개 (타일[3x4]) * 3 = 6개
• 타일(3x2) 1개 + 타일(3x4) 1개 -->  3 * 특수케이스2개 (타일[3x4]) = 6개  
• 타일(3x6) 1개 --> 2개

-> 41개

 

N이 6일 때, 다르게 정리

• 타일(3x2) + 타일(3x4) = 3 * 11 = 33개 (27+6)
• 타일(3x4) + 타일(3x2) = 2 * 3 = 6개 ( 이 위에선 타일(3x4)이 뒤에서만 계산되었기 때문에 앞에서도 경우의 수를 카운트 해줌)
• 타일(3x6) = 특수케이스 2개

-> 고로 이것 또한 41개

---

점화식은 F[N] = ( F[N - 2] * F[2] ) + ( F[N - 4] * 2 ) + ( F[N - 6] * 2) + ( F[N - 8] * 2 ) + ... + ( F[0] * 2 )

 

 

참고 https://yabmoons.tistory.com/536

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

 

이제 구현을 해보자 ! 

import java.io.*;

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

        // N은 1부터 시작하기 때문에 N + 1의 크기를 갖는 배열을 선언한다.
        DP = new int[N+1];

        // 홀수는 불가
        if (N % 2 != 0) {
            System.out.println(0);
            return;
        }

        // 타일이 없을 경우는 1개로 초기화 (이건 임의로 지정)
        DP[0] = 1;
        // 타일이 1개일 경우에는 0개입니다.
        DP[1] = 0;
        // 3x2 타일을 채울 수 있는 경우의 수는 3개이다.
        DP[2] = 3;

        // 짝수 루프입니다.
        for (int i = 4; i <= N; i += 2) {
            DP[i] = DP[i - 2] * DP[2];
            for (int j = i - 4; j >= 0; j -= 2) {
                DP[i] = DP[i] + (DP[j] * 2);
            }
        }

        System.out.println(DP[N]);
    }
}