[백준] 11726 (2×n 타일링)

#1 알고리즘

#1-1 직관화

타일로 생각하면 머리가 아프다. 어떤 수 n을 1과 2만 사용한 덧셈식으로 표현했을 때, 나올 수 있는 가짓수로 생각하면 한결 명확해진다.
 

가령, 위 타일 조합을 1 + 1 + 2 + 1로 생각하는 것이다.
 

#1-2 피보나치?

var n = -1
val cache = Array(1001) { -1 }

fun main() {
    n = readln().toInt()
    
    cache[1] = 1 // (1)
    cache[2] = 2 // (1 + 1), (2)
    cache[3] = 3 // (1 + 1 + 1), (1 + 2), (2 + 1)
    cache[4] = 5 // (1 + 1 + 1 + 1), (1 + 1 + 2), (1 + 2 + 1), (2 + 1 + 1), (2 + 2)
}

cache[1] + cache[2] = cache[3]이고, cache[2] + cache[3] = cache[4]다. 규칙성이 있는 것 '같다 (추측)'. 게다가 주석에 있는 주먹구구식으로 도출한 조합에서도 뭔가(?) 규칙적인 느낌이 난다. 검증해볼 필요가 있다.
 

var n = -1
val cache = Array(1001) { -1 }

fun main() {
    n = readln().toInt()
    
    cache[1] = 1 // (1)
    cache[2] = 2 // (1 + 1), (2)
    cache[3] = 3 // (1 + 1 + 1), (1 + 2), (2 + 1)
    cache[4] = 5 // (1 + 1 + 1 + 1), (1 + 1 + 2), (1 + 2 + 1), (2 + 1 + 1), (2 + 2)
    for (i: Int in 5..1000) {
        cache[i] = cache[i - 1] + cache[i - 2]
    }

    println(cache[n] % 10007)
}

문제에서 n에 9를 넣은 예시 테스트 케이스가 있었고, 그 경우의 정답은 55였다. 위 코드에서도 n에 9를 넣었을 때 55로 잘 나온다.

 

그러나, 해당 코드를 제출했더니 틀렸다는 채점 결과가 나왔다. 로직 자체가 틀린 것은 아닐 테다. 스택 오버플로우 때문일 것이다. cache에 저장할 때부터 나머지 연산을 수행해 저장토록 바꾸면 될 테다.

#2 코드 - 코틀린

var n = -1
val cache = Array(1001) { -1 }

fun main() {
    n = readln().toInt()
    cache[1] = 1 // (1)
    cache[2] = 2 // (1 + 1), (2)
    cache[3] = 3 // (1 + 1 + 1), (1 + 2), (2 + 1)
    cache[4] = 5 // (1 + 1 + 1 + 1), (1 + 1 + 2), (1 + 2 + 1), (2 + 1 + 1), (2 + 2)

    for (i: Int in 5..1000) {
        cache[i] = (cache[i - 1] + cache[i - 2]) % 10007
    }

    println(cache[n] % 10007)
}