[백준/BOJ] 2×n 타일링 2

https://www.acmicpc.net/problem/11727

11727번: 2×n 타일링 2

문제

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

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

해설

앞에서 했던 2×n 타일링에서 좀더 나아간 문제이다.

https://jjunsu.tistory.com/96

[백준/BOJ] 11726번: 2×n 타일링

이 문제 또한 규칙을 찾아 dp를 이용하여 문제를 푼다.

• n=1 -> l
• n=2 -> ll, =, ■
• n=3 -> lll, =l, ■l, l=, l■

n=3일 때 앞에 3개의 경우(lll, =l, ■l)를 보면,

n-1일 때 2*1타일이 세로로 한개 붙은 형태를 뛴다.

나머지 두개(l=, l■)를 보자.

이는 n-2의 경우에 2*1타일을 가로로 두개 붙이거나, 2*2 타일이 한개 붙은 형태를 뛴다.

그림으로 보면 좀 더 쉽게 이해할 수 있을 것이다.

따라서 점화식을 세워보면 다음과 같다.

dp[i] = dp[i-1] + 2 * dp[i-2]

소스 코드

fun main() {
    val n = readLine()!!.toInt()
    val dp = Array(1001) { 0 }
    dp[1] = 1
    dp[2] = 3
    for(i in 3 .. n) dp[i] = (dp[i-1] + dp[i-2] * 2) % 10007
    println(dp[n])
}