[프로그래머스 5단계] 알고리즘 39. 2 x n 타일링

문제 출처는 프로그래머스 알고리즘 연습 에서 볼 수 있습니다!(https://programmers.co.kr/learn/challenges)

알고리즘 39. 2 x n 타일링

1x1 정사각형 2개가 붙어 있는 타일이 있습니다. 이 타일을 이용하여 총 2xN 의 보드판을 채우려고 합니다. 타일은 가로, 세로 두 가지 방향으로 배치할 수 있습니다.

보드판의 길이 N이 주어질 때, 2xN을 타일로 채울 수 있는 경우의 수를 반환하는 tiling 함수를 완성하세요.

예를들어 N이 7일 경우 아래 그림이 타일을 배치할 수 있는 한 경우입니다.

단, 리턴하는 숫자가 매우 커질 수도 있으므로 숫자가 5자리를 넘어간다면 맨 끝자리 5자리만 리턴하세요.예를 들어 N = 2일 경우 가로로 배치하는 경우와 세로로 배치하는 경우가 있을 수 있으므로 2를 반환해 주면 됩니다. 하지만 만약 답이 123456789라면 56789만 반환해주면 됩니다. 리턴하는 숫자의 앞자리가 0일 경우 0을 제외한 숫자를 리턴하세요. 리턴타입은 정수형이어야 합니다.

class TryHelloWorld {

    public int tiling(int n) {

        int answer = 0;

        return answer;

    }

    public static void main(String args[]) {

        TryHelloWorld tryHelloWorld = new TryHelloWorld();

        // 아래는 테스트로 출력해 보기 위한 코드입니다.

        System.out.print(tryHelloWorld.tiling(2));

    }

}

풀이: 

이 문제의 핵심은 조합이다. 먼저 예에서 N=7일 때 총 7개의 타일이 주어진다. 우리가 만들 수 있는 타일링의 개수는 다음과 같이 나눈다. 오른쪽에는 타일링이다. 세로는 1개의 타일로 가로는 2개의 타일로 표현할 수 있다.

• 7개 세웠을 때 | | | | | | |

• 5개 세웠을 때 | | | | | =

• 3개 세웠을 때 | | | = =

• 1개 세웠을 때 | = = =

이 때 가로로 세워진 2개의 타일을 1개의 타일로 보자. 그렇다면 우리가 만들 수 있는 타일링의 경우의 수는 다음과 같다.

• 7개 세웠을 때 Combinate(7, 7)

• 5개 세웠을 때 Combinate(6, 5)

• 3개 세웠을 때 Combinate(5, 3)

• 1개 세웠을 때 Combinate(4, 1)

이 때 규칙은 n이 가로의 길이 즉 타일의 개수, k는 세운 타일의 개수라고 할 때 반복적으로 n은 1개씩 k는 2개씩 감소된다는 것을 알 수 있다. 이 규칙이 짝수의 개수일때도 적용이 되는지 살펴보자. N=8이라고 할 때 타일링의 경우의 수는 다음과 같다.

• 8개 세웠을 때 | | | | | | | | Combinate(8, 8)

• 6개 세웠을 때 | | | | | | = Combinate(7, 6)

• 4개 세웠을 때 | | | | = = Combinate(6, 4)

• 2개 세웠을 때 | | = = = Combinate(5, 2)

• 0개 세웠을 때 = = = = Combinate(4, 0)

역시 반복적으로 n은 1씩 k는 2씩 감소 되는 것을 알 수 있다. 내가 짠 코드는 다음과 같다.

private void combinate(BigInteger[][] dp, int n){

for (int i=0; i<=n; i++){

for (int j=0; j<=n && j<=i; j++){

if (j == 0 || j == i)

dp[i][j] = new BigInteger("1");

else{

dp[i][j] = dp[i-1][j-1].add(dp[i-1][j]);

}

}

}

}

public int tiling(int n) {

int answer = 0;

BigInteger[][] dp = new BigInteger[n+1][n+1];

combinate(dp, n);

BigInteger b = new BigInteger("0");

for (int k=n; k>=0; k-=2){

b = b.add(dp[n--][k]);

}

answer = b.mod(BigInteger.valueOf(100000)).intValue();

return answer;

}

내 코드에서 알아둘 점은 다음과 같다. 

1. combinate 메소드는 처음에 재귀식으로 풀었으나 시간 초과로 실패하게 되어 DP를 활용하여 조합 알고리즘을 완성하였다. 
2. k를 n부터 2씩 빼면은 굳이 n이 홀수인지 짝수인지 알 필요가 없다. 
3. 엄청 큰 수가 저장되기 때문에 BigInteger를 사용하였다.

이 정도만 해두면 5단계까지 푼 여러분은 다 이해할 수 있을 것이라 확신한다. 이 코드보다 간결하게 푸는 방법도 존재하나(피보나치 순열 이용) 따로 설명은 하지 않겠다.