백준 2133 타일 채우기

문제

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

---

코드

import java.io.*;
import java.util.*;

public class Main {
    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));

        //N 입력 받기
        int n = Integer.parseInt(br.readLine());

        //N이 1일 경우
        if(n==1){
            System.out.println(0);
            return;
        }

        //N이 2 이상일 경우
        //0칸을 채우는 경우의 수는 1
        int[] dp=new int[n+1];
        dp[0]=1;
        for(int i=2; i<dp.length; i++){
            //3*2칸을 채우는 총 3가지 경우의 수를 (i-2)칸의 경우의 수*3을 해서 더해준다. 
            dp[i]+=dp[i-2]*3;

            //3*4칸을 채우는 총 2가지 경우의 수를 (i-4)칸의 경우의 수*2를 해서 더해준다.
            //3*6칸을 채우는 총 2가지...
            //4, 6, 8, 10, ... 반복
            for(int j=4; ; j+=2){
                if(i-j>=0)
                    dp[i]+=dp[i-j]*2;
                else
                    break;
            }
        }

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

---

해결 과정

1. 교차해서 쌓는 경우가 4, 6, 8, ...칸마다 2가지 씩이라는 것을 발견 못했었다. 4칸의 경우만 처리해줬다가 틀린 이후 더 있을 수 있는 경우를 생각하다가 알게 됐다.

2. 😁