[코틀린] 11727 __2×n 타일링 2__

1. 마지막에 2×1 타일을 놓는 경우

2. 마지막에 1×2 타일 두 개를 세로로 놓는 경우

3. 마지막에 2×2 타일을 놓는 경우

를 모두 고려한다면, 점화식을 도출이 가능하다.

dp[n] = dp[n-1] + 2 dp[n-2]

package 알고리즘.백준.NX2타일링2

import java.io.BufferedReader
import java.io.InputStreamReader

/**
 *packageName    : 알고리즘.백준.NX2타일링2
 * fileName       : Main
 * author         : ipeac
 * date           : 2024-03-04
 * description    :
 * ===========================================================
 * DATE              AUTHOR             NOTE
 * -----------------------------------------------------------
 * 2024-03-04        ipeac       최초 생성
 */
fun main() {
    BufferedReader(InputStreamReader(System.`in`)).use { r ->
        val n = r.readLine()!!.toInt()
        
        val dp = IntArray(1001) //왠지 모르겠는데 n+1 크기로 잡으니까 ArrayindexOutOfBounds 에러가 발생함.
        
        dp[1] = 1
        dp[2] = 3
        
        if (n <= 2) {
            println(dp[n])
            return
        }
        
        for (i in 3..n) {
            dp[i] = (dp[i - 1] + dp[i - 2] * 2) % 10007
        }
        
        println(dp[n])
    }
}

Uploaded by N2T