[Baekjoon] 타일채우기

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

설명 : 3*N의 타일을 2*1, 1*2 사이즈의 타일을 가지고 채우는 경우의 수를 구하는 문제이다.

풀이 : Top-down 방식으로 해결하면 될 것 같았다. 

그러나 쪼개고 쪼개도 '실패'로 떴고...

생각하지 못했던 부분들까지 쪼개야 하였다. 첨부한 그림파일로 이해하면 쉬울 것이다.

코드 :

 
package feb12.tile;
 
import java.util.Scanner;
 
public class Main {
    
    public static int getTile_2(int n, int[] arr){
        
        if(n <= 2)
            return arr[n];
        else 
            return getTile_2(n - 1, arr) + getTile_2(n - 2, arr);
    }
 
    public static void main(String[] args) {
        // TODO Auto-generated method stub
 
        
        int N;
        Scanner sc = new Scanner(System.in);
        int[] tile_3 = new int[40];
        
        N = sc.nextInt();
        
        tile_3[0] = 1;
        tile_3[2] = 3;
        
        if(N % 2 == 1)
            System.out.println(0);
        else {
            for(int i = 4; i <= N; i += 2){
                tile_3[i] = tile_3[i - 2] * tile_3[2];
                
                for(int j = 4; j <= i; j += 2){
                    tile_3[i] += 2*tile_3[i - j];
                }
            }
            System.out.println(tile_3[N]);
        }
        
        
    }
 
}