tiling 알고리즘

참고링크1 : https://dororongju.tistory.com/100

참고링크2 : DNF LOVE 블로그

---

문제

세로길이가 2, 가로길이가 n인 보드가 있다.

타일의 크기는 2*1 사이즈이다.

주어진 보드를 타일로 채우는 경우의 수를 구하시오.

---

원리

1. 모든 타일을 세로 나열을 하고, 가로 나열이 n개일때 한 칸씩 이동하는 조합의 수를 구하기

2. 주어진 문제에선, 각 타일의 구분이 없다. =  각 타일끼리의 순서는 고려하지 않는다.

---

풀이방법

1. 일반 풀이

: DP가 아닌 방식으로 시도해보았으나 문제가 있다

  1) 중복조합이므로, nHr로 구해보자

  2) 중간에 타일을 중복으로 넣을 수 있음을 고려하지 않았다. => nHr로 계산하기

  3) num이 21까지는 괜찮으나, 이후 오버플로우가 발생하여 문제가 발생한다 ( 오버플로우, 언더플로우 학습하기 )

// TODO: 모든 타일을 세로 나열을 하고, 가로 나열이 n개일때 한 칸씩 이동하는 조합의 수를 구하기
// 무조건 1가지 이상의 경우의 수(num이 1이상의 자연수이므로)

// num이 홀수일 때,
// 반복은 num의 1/2보다 작은 자연수만큼
// 세로방향타일 > 가로방향타일 일때, 세로방향타일개수+1 중 가로방향타일의 개수만큼 뽑는 경우의 수 => nCr = (세로방향타일개수+1)C(가로방향타일개수)
// 세로방향타일 < 가로방향타일 일때, 가로방향타일개수+1 중 세로방향타일의 개수만큼 뽑는 경우의 수 => nCr = (가로방향타일개수+1)C(세로방향타일개수)
// 세로방향타일 = 가로방향타일 일때, 위의 두가지 중 아무쪽이나 상관 없음

// num이 짝수일 때,
// 반복은 num의 1/2을 포함한 자연수만큼
// 세로방향타일 > 가로방향타일 일때, 세로방향타일개수+1 중 가로방향타일의 개수만큼 뽑는 경우의 수 => nCr = (세로방향타일개수+1)C(가로방향타일개수)
// 세로방향타일 < 가로방향타일 일때, 가로방향타일개수+1 중 세로방향타일의 개수만큼 뽑는 경우의 수 => nCr = (가로방향타일개수+1)C(세로방향타일개수)
// 세로방향타일 = 가로방향타일 일때, 위의 두가지 중 아무쪽이나 상관 없음

// num이 홀수 또는 짝수일 때, 반복으로 나온 경우의 수를 모두 더해서 반환

// nCr = n!/(n-r)!

 

2. DP(동적 프로그래밍) = 피보나치

보드의 길이 n이 늘어날 때마다 경우의 수를 나열해보면, 아래와 같다.

n	1	2	3	4	5	6	...
경우의 수	1	2	3	5	8	13	...

즉, 피보나치 수열의 1번째인 0을 제외하고 그대로 간다.

따라서, 이 수열을 식으로 나타내면 tilie( i ) = tile ( i - 1 ) + tile ( i - 2 )로 정의할 수 있다.

만약 Array에 나열한다고 생각하면 0번째, 1번째 숫자는 기본값으로 넣어놓은 상태에서,

tileArr[ i ] = tileArr[ i - 1 ] + tileArr[ i - 2 ] 인 셈이다.

또한, Array는 보드의 길이인 n만큼이다.

단, Array는 인덱스가 0부터 시작이므로, 구하고자하는 n번째 값은 tileArr[ n-1 ]인 셈이다.

즉, n번째 값인 tileArr[ n-1 ]이 곧 n길이의 보드에서 구할 수 있는 경우의 수다.

이게 DP인 이유는 재귀와 반대로 1부터 n까지 순차적으로 값을 생성하는 순방향 구조이기 때문이다.

(재귀는 역방향이다)

---

코드구현

 

 

 

1. 일반 풀이

public class tiling {
    public static void main(String[] args) {
        int num = 5;

        System.out.println(tiling(num));
    }

    public static int tiling(int num) {
        int count = 1;
        
        // num이 짝수일때
        if(num%2==0) {
            for(int i=1 ; i<=num/2 ; i++) {
                int hor = i*2; //가로타일이 차지하는 영역, 가로타일의 개수는 i
                int ver = num-hor; //세로타일의 개수
                if(ver>=i) {
                    // (ver+1) C i = (ver+1)! / ((ver+1)-i)!
                    count += fact(ver+1)/fact((ver+1)-i);
                }
                else if(ver<i) {
                    // (i+1) C ver
                    count += fact(i+1)/fact((i+1)-ver);
                }
            }
        }
        
        // num이 홀수일때
        if(num%2!=0) {
            for(int i=1 ; i<=num/2 ; i++) {
                int hor = i*2;
                int ver = num-hor;
                if(ver>=i) {
                    // (ver+1) C i = (ver+1)! / ((ver+1)-i)!
                    count += fact(ver+1)/fact((ver+1)-i);
                }
                else if(ver<i) {
                    // (i+1) C ver
                    count += fact(i+1)/fact((i+1)-ver);
                }
            }
        }
        return count;
    }

    // 팩토리얼 재귀 식
    public static int fact(int n) {
        if (n <= 1) return n; // 재귀 base 케이스. 즉, 1까지만 곱한단 소리
        else return fact(n-1) * n; // 지금 수*하나 작은 수. 하나 작은 수는 다시 재귀로 하나 더 작은수로 곱을 반복
    }
}

 

2. DP(동적 프로그래밍) = 피보나치

public class tilingDp {
    public static void main(String[] args) {
        int num = 5;

        System.out.println(tiling(num));
    }

    public static int tiling(int num) {
        if(num==1) return 1;
        int [] arr = new int[num];
        arr[0] = 1;
        arr[1] = 2;

        for(int i=2 ; i < num ; i++ ){
            arr[i] = arr[i-1] + arr[i-2];
        }

        return arr[num-1];
    }
}