11444 swift - 피보나치 수 6

 

[종만북] Divide & Conquer / 분할 정복

 

import Foundation

let DIV: UInt = 1000000007
var f = [UInt: UInt]()

func fibo(_ n: UInt) -> UInt {
    if n == 0 { return 0 }
    if n == 1 { return 1 }
    if n == 2 { return 1 }
    
    if let val = f[n] {
        return val
    }
    
    if n % 2 == 0 {
        let m = n / 2
        let temp1 = fibo(m - 1)
        let temp2 = fibo(m)
        f[n] = ((2 * temp1 + temp2) * temp2) % DIV
    } else {
        let m = (n + 1) / 2
        let temp1 = fibo(m)
        let temp2 = fibo(m - 1)
        f[n] = (temp1 * temp1 + temp2 * temp2) % DIV
    }
    return f[n]!
}f

var n = UInt(readLine()!)!
print(fibo(n))