11727번: 2×n 타일링 2

문제 풀이 아이디어

f(n)을 만드는 방법은

1. f(n - 2)에
   1. (2 x 1)를 2개 붙인 정사각형
   2. (2 x 2)의 정사각형을 붙이는 방법과
2. f(n - 1)에 (1 x 2)의 직사각형을 붙이는 방법이 있습니다.

따라서 점화식은 f(n) = f(n - 2) * 2 + f(n - 1)이 됩니다.

코드

var cache = Array(repeating: -1, count: 1001)

func f(_ n: Int) -> Int {
    if n == 1 {
        cache[n] = 1
    }
    
    if n == 2 {
        cache[n] = 3
    }
    
    if cache[n] < 0 {
        cache[n] = (f(n - 2) * 2 + f(n - 1)) % 10007
    }
    
    return cache[n]
}

print(f(Int(readLine()!)!))