Swift - 백준 1003번 피보나치 함수

피보나치 함수 문제는 DP 알고리즘을 사용하면 쉽게 풀 수 있습니다

 

 

아래처럼 피보나치 수열에서 0과 1이 각각 몇번 나오는지 미리 계산을 하지 않으면 시간초과가 발생합니다.

let num = Int(readLine()!)!
var one = 0
var zero = 0

func fibonacci(n: Int) {
    if n == 0 {
        zero += 1
    } else if n == 1 {
        one += 1
    } else {
        fibonacci(n: n-1)
        fibonacci(n: n-2)
    }
}

for _ in 1...num {
    fibonacci(n: Int(readLine()!)!)
    print(zero, one)
    one = 0
    zero = 0
}

 

시간초과를 해결하기 위해서는 이전에 구했던 값을 저장하였다가 다음 값을 구하는데 사용하여 같은 계산을 여러번 반복하지 않도록 하는 것이 중요합니다. 그렇다면 DP 알고리즘을 사용해야 하기 때문에 0부터 4까지 결과값들을 미리 살펴봅니다.

 

N이 0일때: 1 0

N이 1일때: 0 1

N이 2일때: 1 1

N이 3일때: 1 2

N이 4일때: 2 3

 

위에 값들을 자세히 보면 규칙이 존재하는 것을 알 수 있으며 다음과 같이 식으로 코드를 짤 수 있습니다.

let num = Int(readLine()!)!
var arr: [(Int,Int)] = [(1,0),(0,1)]

for i in 2...40 {
    arr.append((arr[i-1].0 + arr[i-2].0, arr[i-1].1 + arr[i-2].1))
}

for _ in 1...num {
    let value = arr[Int(readLine()!)!]
    print(value.0, value.1)
}