[프로그래머스] 피보나치 수 Swift

프로그래머스 - 피보나치 수

나의 풀이

모듈러 연산의 특징

1. ( a mod n + b mod n ) mod n = ( a + b ) mod n
2. ( a mod n - b mod n ) mod n = ( a - b ) mod n
3. ( a mod n x b mod n ) mod n = ( a x b ) mod n

n이 100000이하 자연수이기 때문에 수가 Int, Double을 넘어서 엄청 커져버립니다. 그러니 위의 모듈러 연산의 특징을 따라 처음부터 1234567의 나머지 값으로 계산 해줍시다.

F(3) = F(1) + F(2)
F(3) = F(1) + (F(0) + F(1))
F(3) = F(0) + 2F(1)

F(3) mod 1234567 = (F(0) + 2F(1)) mod 1234567
모듈러 연산을 적용하면
F(3) mod 1234567 = F(0) mod 1234567 + 2F(1) mod 1234567

import Foundation

func solution(_ n:Int) -> Int {
    if n == 0{
        return 0
    }
    if n == 1{
        return 1
    }
    
    var arr: [Int] = [0,1]
    // 재귀함수 쓰면 시간 초과 .. 
    while arr.count <= n{
        arr.append((arr[arr.count - 1] + arr[arr.count - 2]) % 1234567)
    }
    
    return arr[n]
}