백준 2133번 : 타일 채우기 [자바]

 

 

 

🧫 문제 분석

 

✔️ 출처

타일 채우기 골드 4

 

📖 문제

 

홀 수 일때는 만들기가 불가능하다.

크기가 3X2인 벽을 채우는 경우의 수부터 시작한다.  3가지가 있다.

 

현재 크기(i)의 개수 = i - 2번째 크기의 개수 * 3 (이는 이전 크기의 각 구조에 오른쪽으로 3가지 타일을 두는 경우의 수)

또한 특수한 구조가 2가지씩 생긴다.

i - 2번째 크기 * 3 에  특수한 구조 2가지에 대해서 왼쪽에 붙이는 경우의 수를 더한다. 

 

쉽게 이해해본 결과

i = 6 일때

dp [4] * 3 + dp[2] * 2 + dp[0] * 2;

 

dp[2] *2 

dp[4]의 특수한 구조 2가지를 오른쪽에 두고 dp[2]의 구조들을 왼쪽에 채움

 

dp[0] * 2

dp[6]의 특수한 구조 2가지를 오른쪽에 두고, dp[0]의 구조들을 왼쪽에 채움

 

 

 

왜 이렇게 되냐면

원래는 d[i-2] * 3 + dp[i-2] *3 으로 왼쪽, 오른쪽을 3x2 타일로 채우는 방식을 해야하지만

중복이 너무많이 생겨버린다.

 

따라서 dp[i-2] * 3으로 오른쪽을 3x2타일로 채우는 방식으로 경우의 수 를 구하고

중복이 아닌 특수한 구조 2가지에 대해서 dp[i]를 구하는 경우의 수를 구하는 것이다. 

 

 

---

🔅 문제 풀이

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

public class Main {

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

        if (n % 2 != 0) {
            System.out.println(0);
            return;
        }

        int[] dp = new int[n + 1];
        dp[0] = 1; // 아무것도 두지 않으면 되기때문에 1가지 경우의 수가 있다.
        dp[2] = 3;

        // 이전 i-2 도형에 3가지(dp[2])를 오른쪽에 붙이는 모든 경우
        for (int i = 4; i <= n; i+= 2) {
            dp[i] = dp[i-2] * 3;

            // dp[j]: 남은 왼쪽 영역을 채우는 방법의 수
            // i-2k (k >= 2, k += 2) 개수 * (2k 크기의 도형의 특수한 구조  2가지)
            // 각 dp[j]에 대해 오른쪽 2k 칸(i-j)을 특수한 구조 2가지를 붙일 수 있음
            for (int j = i - 4; j >= 0; j -= 2) {
                dp[i] += dp[j] * 2;
            }
        }

        System.out.println(dp[n]);
    }

}

 

 

 

❗ 오답노트 / 필요한 지식

1.  복습 필수다.