백준 2133번 - 타일 채우기

문제

백준 2133번 - 타일 채우기

아이디어

• dp[n]을 3xn 크기일 때 타일을 채울 수 있는 경우의 수라 가정한다.
• 우선 n이 홀수이면 타일을 채울 수 없으므로 경우의 수는 0이다.
• 그리고 3x2 크기는 항상 3가지 경우의 수이다.(세로2가로1, 가로3, 가로1세로2) 그래서 dp[n] = dp[n-2] * 3이 된다.
• 또 하나 생각해야 할 것은 n >= 4 부터는 2가지의 경우의 수가 추가된다는 것이다.
• 즉, 이 문제는 n이 2씩 증가할 때마다 3가지의 경우의 수가 추가되는 기본 패턴과 n이 4 이상일 때 2개의 경우의 수가 추가되는 추가 패턴을 고려하여 해결해야 한다.
• 최종 점화식은 다음과 같다.
• dp[n] = dp[n-2] * 3 + dp[n-(2,4,6,8...)] * 2
• (솔직히 아직 제대로 이해하지 못했다.ㅠㅠ)

예상 시간 복잡도

• 예상 시간 복잡도 : O(N^2)

코드 구현

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

public class BJ_2133 {
    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 == 1) {
            System.out.println(0);
            return;
        }

        int[] dp = new int[n + 1];

        dp[0] = 1;

        for (int i = 2; i <= n; i += 2) { //홀수는 볼 필요 없음
            dp[i] = dp[i - 2] * 3; //기본 패턴

            for (int j = 4; j <= i; j += 2) {
                dp[i] += 2 * dp[i - j]; //추가 패턴
            }
        }

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