[백준 11727번] 2×n 타일링 2 - Kotlin

[백준 11727번] 2×n 타일링 2 - Kotlin

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

---

문제

• 2×n 직사각형을 1×2, 2×1과 2×2 타일로 채우는 방법의 수를 구하는 프로그램을 작성하시오.
• 아래 그림은 2×17 직사각형을 채운 한가지 예이다.

---

입력

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

---

출력

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

---

풀이

private class Solution11727 {
    fun solution(n: Int): Int {
        // n = 2 -> 2 * 2, (2 * 1) * 2, (1 * 2) * 2
        val dp = IntArray(n + 1) {
            when (it) {
                1 -> 1
                2 -> 3
                else -> 0
            }
        }

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

        return dp[n]
    }
}

private fun main() {
    val br = System.`in`.bufferedReader()
    val bw = System.out.bufferedWriter()

    val n = br.readLine().toInt()

    bw.append("${Solution11727().solution(n)}\n")
    bw.flush()

    br.close()
    bw.close()
}