(Swift) 백준 11727 2xn 타일링 2

SteadySlower·2022년 7월 15일
0

Coding Test

목록 보기
95/305

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()!)!))
profile
백과사전 보다 항해일지(혹은 표류일지)를 지향합니다.

0개의 댓글