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

문제

 

11726번: 2×n 타일링

 

---

풀이

 

 문제를 보고 일단 타일의 모습을 그려보기로 했다.

 

 n의 타일은 n - 1 의 타일에 세로 타일이 하나씩 추가된 모습과, n - 2의 타일에 가로 타일 두개씩 추가된 모습이다, 이를 점화식으로 나타내면 dp[n] = dp[n - 1] + dp[n - 2] 이다. 이 점화식을 이용해 문제를 해결하면 된다.

 

---

코드

 

fun main() {
    val br = System.`in`.bufferedReader()
    val bw = System.out.bufferedWriter()
 
    val mod = 10007
    val num = br.readLine().toInt()
    val dp = IntArray(1001)
 
    dp[1] = 1
    dp[2] = 2
 
    for(i in 3 .. num) {
        dp[i] = (dp[i - 1] + dp[i - 2]) % mod
    }
 
    bw.write("${dp[num]}")
    bw.flush()
    bw.close()
    br.close()
}