[Algorithm] 피보나치 수 (동적계획법, 모듈러 연산)

🖥 문제

문제 설명

피보나치 수는 F(0) = 0, F(1) = 1일 때, 1 이상의 n에 대하여 F(n) = F(n-1) + F(n-2)가 적용되는 수입니다.
예를 들어
F(2) = F(0) + F(1) = 0 + 1 = 1
F(3) = F(1) + F(2) = 1 + 1 = 2
F(4) = F(2) + F(3) = 1 + 2 = 3
F(5) = F(3) + F(4) = 2 + 3 = 5
와 같이 이어집니다.
2 이상의 n이 입력되었을 때, n번째 피보나치 수를 1234567로 나눈 나머지를 리턴하는 함수, solution을 완성해 주세요.

제한 사항

• n은 1 이상, 100000 이하인 자연수입니다.

🤔 풀이 방법

1. var fibo: [Int] = Array(repeating: 0, count: n + 1)
   • n번째 피보나치 수를 구하기 위하여 n + 1 길이의 배열을 만든다.
   • 5번째 피보나치 수를 구하려면 0 ~ 5까지 총 6개의 배열이 필요하기 때문이다.
2. fibo[i] = (fibo[i - 2] + fibo[i - 1]) % 1234567
   • (n - 2)를 A, (n - 1)을 B, 1234567을 C라고 할 때, n % C는 (A + B) % C이다.
   • 모듈러 연산의 성질 (A + B) % C = ((A % C) + (B % C)) % C를 이용하여 결과를 구한다.

👩🏻‍💻 Swift Code

import Foundation

func solution(_ n:Int) -> Int {
    var fibo: [Int] = Array(repeating: 0, count: n + 1)
    fibo[1] = 1

    for i in 2...n {
        fibo[i] = (fibo[i - 2] + fibo[i - 1]) % 1234567
    }

    return fibo[n]
}

 

 

코딩테스트 연습 - 피보나치 수