[백준/코틀린] 11726번: 2×n 타일링

링크

11726번: 2×n 타일링

풀이

dp[i]: 2xn 크기의 직사각형을 1x2, 2x1 타일로 채우는 방법의 수

2xn 크기의 직사각형을 만드는 방법은 두 가지입니다.
- 2x(n-1) 크기의 직사각형 뒤에 2x1 타일을 1개 붙이는 경우
- 2x(n-2) 크기의 직사각형 뒤에 1x2 타일을 2개 붙이는 경우

즉, dp[i] = dp[i - 1] + dp[i - 2]이 됩니다.

코드

fun main() {
    val mod = 10007
    val n = readln().toInt()
    val dp = MutableList(1001) {
        when (it) {
            1 -> 1
            2 -> 2
            else -> 0
        }
    }

    (3..1000).forEach {
        dp[it] = (dp[it - 1] + dp[it - 2]) % mod
    }

    println(dp[n])
}