[백준(BOJ)] 9711 피보나치 - 스위프트(Swift)

[Silver III] 피보나치 - 9711

문제 링크

성능 요약

메모리: 79720 KB, 시간: 988 ms

분류

다이나믹 프로그래밍, 수학

문제 설명

피보나치 수열은 아래와 같이 표현된다.

1, 1, 2, 3, 5, 8, 13, 21, 34, ...

각 숫자는 앞의 두 숫자의 합으로 나타내는 것을 알 수 있다.

P와 Q 그리고 n이 주어질 때, P번째 피보나치 숫자를 Q로 나눈 나머지를 구하여라.

입력

첫 번째 라인에는 정수 T개의 테스트 케이스가 주어진다.

각 테스트 케이스는 정수 P와 Q가 주어진다.

출력

각 테스트 케이스마다 "Case #x: M" 형식으로 출력한다.

x는 테스트 케이스 번호(1부터 시작), M은 P번째 피보나치 숫자를 Q로 나눈 나머지이다.

 

풀이

i)

첫 시도에서는 P의 최대값을 구하고, 최대값 범위까지의 피보나치 배열을 생성하고 계산을 하고자 하였습니다.

import Foundation

let N = Int(readLine()!)!
var (P, Q) = ([Int](), [Int]())
var fibonachi: [Int64] = [1, 1]

for _ in 0..<N {
    let input = readLine()!.split(separator: " ").map { Int($0)! }
    P.append(input[0])
    Q.append(input[1])
}

let maxP = P.max()!

for i in 2..<maxP {
    fibonachi.append(fibonachi[i-2] + fibonachi[i-1])
}

→ Thread 1: Swift runtime failure: arithmetic overflow

연산의 범위가 너무 커져서 에러가 나타났습니다.

 

ii)

그래서 전체를 더하지 말고, 만약 q보다 큰 숫자가 나타나면 바로 나눈 다음 나머지를 대입하는 방식을 생각하였습니다.

구하고자 하는 값이 어차피 나머지를 구하는 것이기 때문에 나머지를 통해 계산을 진행해도 결과는 같을 것이라 생각했습니다.

import Foundation

let N = Int(readLine()!)!

for i in 0..<N {
    let input = readLine()!.split(separator: " ").map { Int($0)! }
    print("Case #\(i+1): \(divideFib(p: input[0], q: input[1]))")
}

func divideFib(p: Int, q: Int) -> Int {
    var fibonachi: [Int] = [1, 1]

    for i in 2..<p {
        fibonachi.append(fibonachi[i-2] + fibonachi[i-1])
        if fibonachi[i] >= q {
            fibonachi[i] %= q
        }
    }
    return fibonachi[p-1]
}

→ Thread 1: Fatal error: Range requires lowerBound <= upperBound 

해당 에러문은 스위프트에서 특히? 주의해야하는 것인데, if문의 분기처리를 확실하게 해주어야 에러가 나타나지 않습니다.

for i in 2..<p를 보면 P가 2 이상인 경우만 존재하는데, p가 0이나 1의 경우일 때는 처리할 수 없게 되어 에러로 나타나게 됩니다.

 

따라서 해당 식에 대한 분기처리를 진행해줘야 합니다.

 

iii)

if문의 분기 처리

let N = Int(readLine()!)!

for i in 0..<N {
    let input = readLine()!.split(separator: " ").map { Int($0)! }
    print("Case #\(i+1): \(divideFib(p: input[0], q: input[1]))")
}

func divideFib(p: Int, q: Int) -> Int {
    var fibonachi: [Int] = [1, 1]

    if p <= 2 {
        return fibonachi[p-1] % q
    }
    if p > 2 {
        for i in 2..<p {
            fibonachi.append(fibonachi[i-2] + fibonachi[i-1])
            if fibonachi[i] >= q {
                fibonachi[i] %= q
            }
        }
    }
    return fibonachi[p-1]
}