백준 11727 - 2 X N 타일링 2

 

2*n타일링 문제에서 채울 수 있는 타일 2*2가 추가 된 것이다.

 

이제 2*2 타일은 2*1과 1*2와 2*2타일로 채울 수 있다.  3가지 타일로 

 

다른 2*n타일로 마찬가지로 n-1타일에 2*1타일 추가 n-2타일에 1*2위아래 추가 n-2타일에 2*2타일 추가의 경우의 수로 

2*n타일을 채우는 경우의 수를 생각할 수 있으니

 

점화식은 

D[n] = D[n-1]+D[n-2]+D[n-2]이다.

 

상태:N , 종료조건 : 0일때는 0 1일때 1개 2일때 3개 return

 

import java.io.BufferedReader;
import java.io.InputStreamReader;
public class Main {
    public static int[] d;
    public static void main(String[] args) throws Exception{
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));

        int n = Integer.parseInt(br.readLine());
        d = new int[n+1];
        d[1]=1;

        System.out.print(two_n(n));


      }

    public static int two_n(int n){
       if(n == 0) return 0;
       if(n == 2) return  3;
       if(d[n] > 0) return d[n];

       d[n] = two_n(n-1) + two_n(n-2) + two_n(n-2);
       d[n] %= 10007;
       return d[n];
    }

}