BOJ-11444 피보나치 수 6 Swift

문제

피보나치 수는 0과 1로 시작한다. 0번째 피보나치 수는 0이고, 1번째 피보나치 수는 1이다. 그 다음 2번째 부터는 바로 앞 두 피보나치 수의 합이 된다.

이를 식으로 써보면 Fn = Fn-1 + Fn-2 (n ≥ 2)가 된다.

n=17일때 까지 피보나치 수를 써보면 다음과 같다.

0, 1, 1, 2, 3, 5, 8, 13, 21, 34, 55, 89, 144, 233, 377, 610, 987, 1597

n이 주어졌을 때, n번째 피보나치 수를 구하는 프로그램을 작성하시오.

입력

첫째 줄에 n이 주어진다. n은 1,000,000,000,000,000,000보다 작거나 같은 자연수이다.

출력

첫째 줄에 n번째 피보나치 수를 1,000,000,007으로 나눈 나머지를 출력한다.

내가 푼 풀이

문제를 보았을때 이문제는 수학적 성질이 요구되는 문제일꺼다 생각했다

Swift 언어로 문제를 풀기에는 입력수를 담을 배열을 선언할 수도 없고, 입력값이 너무커서 분할정복을 이용한 재귀호출도 시간초과가 떴다.

다른사람의 풀이를 참고했다.

 

접근방법: 분할정복, 피보나치수열의 성질

보통 피보나치 수열의 도가뉴항등식을 이용하여 분할정복을 했지만, 입력값이 너무커서 시간초과가 났다

도가뉴 항등식

$F_{m+n} = F_{m-1}F_{n} + F_{m}F_{n+1} $

 

주어진 n이 짝수일때 m = n:

$F_{2n} = F_{n-1}F_{n} + F_{n}F_{n+1} $ = $F_{n}( F_{n-1} + F_{n+1})$

여기서 $F_{n+1} = F_{n} + F_{n-1}$ 이므로

$F_{n}( F_{n-1} + F_{n+1})$ = $F_{n}(2F_{n-1} + F_{n})$ 로 나타낼 수 있다.

 

주어진 n이 홀수일때 m = n+1:

$F_{2n+1} = F_{n}F_{n} + F_{n+1}F_{n+1} $  = $F_{2n+1} =(F_{n})^{2} + (F_{n+1})^{2}$

 

따라서 n이 홀수일때와 짝수일때 분할정복하여 결과를 출력했었는데... 시간초과가 났다

<시간초과 코드>

import Foundation

// 입력
var n = Int(readLine()!)!
let p = 1000000007

// 분할 정복
func divide(_ n: Int) -> Int {
    if n == 0 { return 0}
    if n == 1 { return 1}
    if n == 2 { return 1}
    let m = divide(n/2)
    if n % 2 == 0 {
        let m1 = divide(n/2-1)
        return m * (2 * m1 + m) % p
    } else {
        let m1 = divide(n/2 + 1)
        return ((m * m) + (m1 * m1)) % p
    }
}
print(divide(n))

아무래도 재귀호출이 너무남발되어 시간초과가 날꺼라 생각하고, 이를 dp형식으로 배열에 저장하고 값을 불러오자 하여 바꾸어보았다.

그래도 시간초과가 일어났다.

import Foundation

// 입력받기
var n = Int(readLine()!)!
let p = 1000000007
// 초기값 설정
var dp = Array(repeating: 0, count: n+3)
dp[0] = 0
dp[1] = 1
dp[2] = 1

// 분할 정복
func divide(_ n: Int) -> Int {
    if n == 0 || n == 1 || n == 2 { return dp[n] }
    let m = divide(n/2)
    if n % 2 == 0 {
        let m1 = divide(n/2-1)
        dp[n] = m * (2 * m1 + m) % p
    } else {
        let m1 = divide(n/2 + 1)
        dp[n] = ((m * m) + (m1 * m1)) % p
    }
    return dp[n]
}
print(divide(n))

위 두개의 코드는 재귀호출 수는 차이가 없어보이는데 아래 dp배열을 이용한것은 입력값만큼의 수를 담을 배열을 만들 수가 없었다.

그래서 런타임에러가 떴다..

다른 언어는 잘만되는데 ;

 

그러다가 피보나치수열을 행렬의곱셈으로 구하는 방법을 찾아보게되었다.

https://www.acmicpc.net/blog/view/28

 

행렬의 곱셈으로 피보나치수열을 구하는방법인데 이 방법은 위 방법과 다르게 입력값크기의 배열을 구현하지 않아도 되고, 재귀호출도 남발하지 않게된다.

import Foundation

// 입력
var n = Int(readLine()!)!
let p = 1000000007
// 피보나치 수열을 행렬곱셈으로 구하기
var arr: [[Int]] = [[1,1],[1,0]]

// 행렬 곱셈
func multi(_ x: [[Int]],_ y: [[Int]]) -> [[Int]]{
    var result = Array(repeating: Array(repeating: 0, count: 2), count: 2)
    for i in 0..<2 {
        for j in 0..<2{
            for k in 0..<2 {
                result[i][j] += x[i][k] * y[k][j]
                result[i][j] %= p
            }
        }
    }
    return result
}
//
// 분할 정복
func divide(_ n: Int) -> [[Int]] {
    // n이 1이면 배열 리턴
    if n == 1 { return arr }
    
    // n이 1이될때까지 분할
    let m = divide(n/2)
    if n % 2 == 0 {
        return multi(m,m)
    } else {
        return multi(multi(m,m), arr)
    }
}
// 출력
print(divide(n)[0][1])

 

참 수학의 세계는 어렵다..