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

date

Aug 24, 2023

slug

boj-2133

author

status

Public

문제링크

2133번: 타일 채우기

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

https://www.acmicpc.net/problem/2133

1. 아이디어

타일 채우기 문제 -> dp로 접근하자, bottom-up 방식

dp[i] = 3 * i 타일을 채울 수 있는 방법의 수

일단 홀수면 방법 없음, 0출력

N = 2n+1 (n=0,1,2,…)
3*N = 3(2n+1) = 6n+3 = 2(3n+1)+1 = 2k+1 = 홀수
홀수 면적은 2*1 타일로 채울 수 없으므로 가능한 경우의 수 = 0

짝수면

dp[i] = dp[i-2]*3 //이전 단계에3*2짜리 붙이기

+ (dp[i-4]+dp[i-6]+dp[i-8]...)*2 (계속해서 새로 생기는 케이스 역순 배치)
+ 2 //새로 생기는 케이스

초기값 설정

dp[1] = 0
dp[2] = 3

2. 시간복잡도

2중for문 ⇒ O(N^2)

3.자료구조

int[N] dp

코드


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

public class Main_BOJ_2133_타일채우기_G4 {
    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        int N = Integer.parseInt(br.readLine());

        // 만약 홀수라면 방법 없음, 0 출력
        if(N%2==1) {
            System.out.println(0);
            return;
        }

        // dp 시작
        int[] dp = new int[N+1];
        dp[2] = 3;

        for (int i = 4; i <= N; i+=2) {
            dp[i] = dp[i-2]*3+2;
            for (int j = 2; j < i-2; j++) {
                dp[i]+=dp[j]*2;
            }
        }
        System.out.println(dp[N]);
    }
}