[Backjoon] 11727번 문제 - 2xn 타일링 2

2×n 직사각형을 2×1과 2×2 타일로 채우는 방법의 수를 구하는 프로그램을 작성하시오.

아래 그림은 2×17 직사각형을 채운 한가지 예이다.

풀이

경우의 수 문제이다.

우선 2Xn 직사각형에서 n이 1일때 부터 생각해보면 경우의 수는 1가지 이다.

n이 2일 때 타일을 채우는 경우의 수는 3가지이다.

n이 3일때부터 앞에서 구해진 2x1과 2x2를 기반으로 생각할수 있는데, 

2x1타일로 먼저 채울 경우와 2x2타일로 먼저 채우는 경우의 수로 나뉜다.

위의 그림 처럼 모든 경우의 수를 고려 했을 때 중복되는 경우의 수를 빼면 타일의 경우의 수가 나오는 것이다.

즉 2x3타일을 채우기 위해서는

2x3-2x1으로 채워졌다는 가정하에 2x2만 더 채우면 되므로 2x2의 경우의 수 만큼 더해주면되고

2x3-2x2으로 채워졌다는 가정하에 2x1만 더 채우면 되므로 2x1의 경우의 수만큼 더해주면 된다.

결과적으로 arr[1]=1, arr[2]=3이라고 할때

arr[3] = arr[3-1]+3*[3-2]-중복 으로 나타낼 수 있다.

중복은 2x2타일 경우의 수에서 2x1과 동일한 세로 타일 때문에 발생하는 것인데,

이는 해당 경우의 수의 제일 앞에있는 2x1때문에 발생한다.

따라서 중복은 arr[i-2]가 되기 때문에

arr[i] = arr[i-1]+3*arr[i-2]-a[i-2]에서 최종적으로

arr[i] = arr[i-1]+2*arr[i-2]라는 식이 나오게 된다.

참고로 아래에서 반복문 안에서 배열에 넣기전에 10007로 나눠주는것은 

모든 연산이 끝나고 나눠주게 되면 범위 초과로 틀렸다는 답이 나오기 때문이다.

import java.util.Scanner;
 
public class Main {
    public static void main(String[] args){
        Scanner sc = new Scanner(System.in);
        int size = sc.nextInt();
        int[] arr = new int[size];
        int result = 0;
 
        if(size==1){
            System.out.println(1);
            return;
        }
 
        arr[0] = 1;
        arr[1] = 3;
 
        for(int i=2; i<size; i++){
            arr[i] = (arr[i-1]+(2*arr[i-2]))%10007;                                                      
        }
 
        result = arr[size-1];
 
        System.out.println(result);
    }
}