[Kotlin] 백준(BOJ) 11727 2xn 타일링 2

문제 전문은 아래 버튼을 눌러 확인하실  수 있습니다.

문제

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

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

 

입력

첫째 줄에 n이 주어진다. (1 ≤ n ≤ 1,000)

 

출력

첫째 줄에 2×n 크기의 직사각형을 채우는 방법의 수를 10,007로 나눈 나머지를 출력한다.

 

예제 입출력

 

문제 해설

비슷한 문제를 수업시간에 배웠던 적이 있어 그 방법을 이용하여 해결했다. 약간 분할 정복 느낌으로 점화식을 도출할 수 있다. 

 

 $2 \times n$ 직사각형의 마지막을 채우는 방법은 다음과 같다

 

세로 $2 \times 1$ 타일 1개 

이 경우 앞의 직사각형을 채우는 경우는 $dp[n-1]$이다. 

 

가로 $1 \times 2$ 타일 2개

이 경우 앞의 직사각형을 채우는 경우는 $dp[n-2]$이다. 

 

$2 \times 2$ 타일 1개 

이 경우 앞의 직사각형을 채우는 경우는 $dp[n-2]$이다. 

 

위 경우를 더한 것이 전체 경우의 수이므로, $dp[n] = dp[n-1] + 2 \times dp[n-2]$ 라는 점화식을 도출할 수 있다.

 

또한 $n$이 $1$일 때 전체 경우의 수는  세로 $2 \times 1$ 타일 $1$개 뿐이므로 $1$, 

$2$일 경우는 위 마지막 타일을 채우는 경우와 동일한 경우의 수이므로 $3$이다. 

 

위 로직을 다음과 같이 구현할 수 있다.

소스 코드

fun main() {
    val n = readln().toInt()
    val MOD = 10007

    val dp = IntArray(n + 1)

    dp[1] = 1 // 기저값
    if (n >= 2) dp[2] = 3

    for (i in 3..n) {
        dp[i] = (dp[i - 1] + 2 * dp[i - 2]) % MOD
    }

    println(dp[n])
}

 

시간 복잡도

for문에서 상수번 연산을 수행하므로, 

코드의 전체 시간 복잡도는 $O(N)$ 이라고 할 수 있겠다.