TIL #86

백준 11726번
2xn 타일링

2xn 크기의 직사각형을 1x2, 2x1타일로 채우는 방법의 수를 모두 구한다.

못풀어서 다른사람의 풀이를 참고했는데 손으로 풀어보면 점화식 dp[i] = dp[n-1] + dp[n-2]로 나타낼 수 있다.
이를 이용해 풀면된다.

풀이

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

처음에 1아래 값의 처리를 안해줘 배열생성에서 dp[2] = 2를 해줄때 런타임 오류가 발생했었음