[백준/JAVA] 2133번 타일 채우기

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

1. 문제

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

2. 힌트

3. 문제 접근

1) 첫째 줄에 N의 크기를 입력받는다.
2) 경우의 수를 고려한 후 다이나믹 프로그래밍에 대한 점화식을 세운다.
2-1) 홀수인 경우 칸의 총 수가 홀수이기 때문에 2X1 혹은 1X2 크기의 타일로 채우지 못하기 때문에 0을 반환한다.
2-2) 짝수인 경우 크기가 2 작은 타일에서 채우는 경우의 수가 3가지이기 때문에 N-2를 매개변수로 하는 재귀함수에 3을 곱하는 경우를 가진다.
2-3) 짝수인 경우 중에 크기가 2보다 큰 짝수(4,6,8)만큼 작은 타일에서 채우는 경우의 수가 2가지이기 때문에 N-(2보다 큰 짝수)를 매개변수로 하는 재귀함수에 2를 곱하는 경우의 수도 가진다.
3) 점화식을 세워서 함수를 실행한다.

4. 코드

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

public class Main {
    static int tile[];
    public static void main(String[] args) throws IOException{
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        int N = Integer.parseInt(br.readLine());
        tile = new int[N+1];
        int result = Solution(N);
        System.out.println(result);
    }
    static int Solution(int n) {
        if(n==0) {
            return 1;
        }
        if(n%2==1) {
            return 0;
        }
        if(n==2) {
            return 3;
        }
        if(tile[n]!=0) {
            return tile[n];
        }
        int temp = n-2;
        while(temp>0) {
            tile[n] += 2*Solution(temp-2);
            temp-=2;
        }
        return tile[n] += Solution(n-2) * 3;
    }
}