[백준] 2 * n 타일링(DP 풀이)

---

백준 온라인 저지 11726번 - 2*n 타일링

지난 동적 계획법 알고리즘 포스팅에서 공부한 것을 적용하기 위해 간단한 동적 계획법을 활용한 문제를 풀이했다.

풀이 및 점화식 도출 과정은 하기와 같다.

1. 아래와 같이 2 x 5(5는 문제에서의 n)의 직사각형에서 2 x 1 또는 1 x 2의 타일을 채우는 경우의 수를 구한다고 가정(이 때 n - 1, 2, 3, 4의 타일을 채우는 경우의 수는 모두 다 알고 있다고 가정)

⬛️⬛️⬛️⬛️⬛️
⬛️⬛️⬛️⬛️⬛️

2. 2 x 4의(n - 1) 타일 채우는 경우의 수를 모두 알고 있다고 가정하면 2 x 1(세로)로 타일을 채워 2 x 5 직사각형을 만들 수 있음(경우의 수 한 개)

⬛️⬛️⬛️⬛️⬜️
⬛️⬛️⬛️⬛️⬜️

3. 2 x 3의(n - 2) 타일 채우는 경우의 수를 모두 알고 있다고 가정하면 2 x 1 두 개(세로) 또는 1 x 2 두 개(가로)로 타일을 채워 2 x 5 직사각형을 만들 수 있으나 사실 2 x 4의 타일 채우는 경우의 수에서 2 x 1 두 개(세로)의 경우는 나오기 때문에 1 x 2 두 개(가로)로 타일을 채워 2 x 5 직사각형을 만들 수 있음(경우의 수 한개)

⬛️⬛️⬛️⬜️⬜️
⬛️⬛️⬛️⬜️⬜️

4. 결국 2번 과정(n - 1)과 3번 과정(n - 2)의 경우의 수의 합이 n의 경우의 수가 된다.

따라서, 아래와 같은 점화식이 도출된다.

D[n] = D[n - 1] + D[n - 2]

위 점화식을 바탕으로 아래와 같이 풀이하였다.

1. 2 x n에서 n이 1일때는 2 * 1 타일 하나로 채우는 방법만 존재하는 것을 알기 때문에 D[1]을 1로 초기화
2. 2 x n에서 n이 2일때는 2 1 타일 두 개 또는 1 2 타일 두 개로 채우는 방법만 존재하는 것을 알기 때문에 D[2]을 2로 초기화
3. 초기화한 값을 바탕으로 점화식(바텀업 방식 - 반복문 사용) + 문제에서 요구한 10007로 나눈 나머지 조건을 통해 결과 도출

Tiling2N.java

package com.example.Baekjoon;

/**
 * 백준 온라인 저지 11726 - 2 * n 타일링
 * 동적 계획법 사용하여 풀이
 */
public class Tiling2N {
    public int dp(int tileWidth) {
        int[] D = new int[tileWidth + 1];

        // 가장 작은 문제 초기화
        D[1] = 1; // 너비가 1의 직사각형의 경우 1 * 2 또는 2 * 1 타일로 채울 수 있는 경우의 수는 1개
        D[2] = 2; // 너비가 2의 직사각형의 경우 1 * 2 또는 2 * 1 타일로 채울 수 있는 경우의 수는 2개

        /**
         * 바텀업 방식으로 풀이
         * 점화식 D[N] = D[N - 1] + D[N - 2]
         */
        for (int i = 3; i < D.length; i++) {
            D[i] = (D[i - 1] + D[i - 2]) % 10007;
        }

        return D[tileWidth];
    }
}

Tiling2NTest.java

package com.example.Baekjoon;

import static org.junit.Assert.assertEquals;

import org.junit.Test;

public class Tiling2NTest {
    @Test
    public void testTiling2N() {
        Tiling2N t = new Tiling2N();

        int result1 = t.dp(2);
        int result2 = t.dp(9);

        assertEquals(2, result1);
        assertEquals(55, result2);
    }
}