백준 11726 - 2 X N 타일링

 

2*N 사이즈의 사각형을  2*1 타일 혹은 1*2타일로 채우는 방법의 경우의 수를 찾는 문제이다.

 

- 먼저 상태와 종료조건을 생각해보자. => 상태 N , 종료조건 : ?

 

변하지 않는 것: 각 2*N의 타일을 채우는 경우의 수 가령 2*2타일을 채운다면, 2*1 옆으로 두개 1*2위아래로 두개씩 채울 수 있는 경우의 수 2가지 등 2*N의 타일을 채우는 경우의 수를 찾는 과정에서 생기는 2*N-1 ....2*1을 채우는 경우의 수는 변하지 않을 것이다.

 

이제 큰 문제를 작은 문제로 쪼개서 생각해보자. 

2*N타일을 채우는 과정에서 2*n-1 ..2*n-2.. 2*n-3의 타일들을 채우는 경우의 수가 변하지 않는다면, 이를 활용할 수 있을 것이다. 

2*N-1타일에서 2*1타일 하나가 추가된 모양이 2*N타일이라면, 2*N을 채우는 경우의 수는 2*n-1을 채우는 경우의 수와 같을 것이다

가령 2*3을 만드는 경우의 수가 2*2에 2*1타일을 하나 더한 모양이라면, 갯수가 중요한게 아니라 경우의 수가 중요하므로 2*2를 만드는 경우의 수와 2*3을 만드는 경우의 수가 같을 것이다.

또한 2*N타일이 2*N-2타일에서 1*2타일 두개를 추가한 모양이라면, 2*N을 채우는 경우의 수는 2*N-2타일을 추가하는 경우의 수와 동일 할 것이다.

가령 2*3을 만드는 경우의 수가 2*1에서 1*2 두개를 추가한 모양이라면, 2*3을 만드는 경우의 수는 2*1을 만드는 경우의 수와 같다.

 

따라서 우리는 2*N타일을 만들기 위해 2*N-1타일 2*1타일을 하나 추가하거나  2*N-2타일에 1*2타일 두개를 위아래로 추가해서 만들 것이므로, 2*N타일을 만들기 위한 경우의 수는 2*N-1을 만드는 경우의 수에 2*N-2를 만드는 경우의 수를 더한 것과 같다.

 

점화식 D[N] = D[N-1] + D[N-2]

 

종료조건 : 2*0타일을 만드는 경우의 수는 없으므로 0 return, 2*1타일을 만드는 경우의 수는 1개이므로 1 return 

2*2 타일을 만드는 경우의 수는 2개이므로 2 return

 

 

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 2;
        if(d[n] > 0) return d[n];

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

}

결과를 10007로 나눈 것을 return하라고해서 나눠주었다.

d[2] =2 로 저장하고 시작하지 않은 것은 n=1일때 예외발생한다.