[백준 온라인 저지] 2133. 타일 채우기

3*n 크기의 직사각형을 1*2, 2*1 타일로 채우려고 한다.

 

1. 입력

- 첫째 줄에 n이 주어진다. (1 ≤ n ≤ 30)

- n이 직사각형의 가로다.

 

2. 출력

- 첫째 줄에 경우의 수를 출력한다.

 

3. 예제

 

4. 코드

1) 잘 안풀려서 제시된 c++ 코드를 java로 바꿔서 돌려본 코드

import java.util.*;
class Main{
    public static void main(String[] args){
        int n = new Scanner(System.in).nextInt();
        int[] d = new int[n+1];
        System.out.print(dp(n, d));
    }
    
    static int dp(int x, int[] d){
        if(x%2==1) return 0;
        if(x==0) return 1;
        if(x==2) return 3;
        if(d[x]!=0) return d[x];
        d[x] = 3*dp(x-2, d);
        for(int i=4 ; i<=x ; i+=2)
            d[x] += 2*dp(x-i, d);
        return d[x];
    }
}

- 가로를 n-2까지 채웠다고 했을 때 나머지 2를 채우는 경우의 수는 3가지가 있고, n이 4 이상일 때 2의 배수일때마다 고유한 모양이 2가지가 나타난다.

- 따라서 점화식을 쓰면 d[i] = 3*d[i-2] + 2*(d[i-4] + d[i-6] + ... + d[0])

 

2) 재귀 함수 없이 구현한 코드

import java.util.*;
class Main{
    public static void main(String[] args){
        int n = new Scanner(System.in).nextInt();
        if(n%2==1) System.out.print(0);
        else{
            int[] d = new int[n+1];
            d[0] = 1; d[2] = 3;
            for(int i=4 ; i<=n ; i+=2){
                d[i] = 3*d[i-2];
                for(int j=4 ; j<=i ; j+=2)
                    d[i] += 2*d[i-j];
            }
            System.out.print(d[n]);
        }
    }
}

- 메모리는 1번보다 아주 약간 더 사용했지만 속도도 그만큼 빨라졌다.