1904번: 01타일

문제 풀이 아이디어

길이가 N인 이진수열을 만들기 위해서는

1. 길이가 N - 2인 이진수열에 “00” 붙이거나
2. 길이가 N - 1인 이진수열에 “1”을 붙이는 방법이 있습니다.

따라서 점화식은 f(n) = f(n - 2) + f(n - 1)로 피보나치 수열과 동일합니다.

코드

// 01타일

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

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

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