[백준] 1003번 피보나치 함수 [Swift]

문제 링크

1003번: 피보나치 함수

문제

다음 소스는 N번째 피보나치 수를 구하는 C++ 함수이다.

int fibonacci(int n) {
    if (n == 0) {
        printf("0");
        return 0;
    } else if (n == 1) {
        printf("1");
        return 1;
    } else {
        return fibonacci(n‐1) + fibonacci(n‐2);
    }
}

fibonacci(3)을 호출하면 다음과 같은 일이 일어난다.

• fibonacci(3)은 fibonacci(2)와 fibonacci(1) (첫 번째 호출)을 호출한다.
• fibonacci(2)는 fibonacci(1) (두 번째 호출)과 fibonacci(0)을 호출한다.
• 두 번째 호출한 fibonacci(1)은 1을 출력하고 1을 리턴한다.
• fibonacci(0)은 0을 출력하고, 0을 리턴한다.
• fibonacci(2)는 fibonacci(1)과 fibonacci(0)의 결과를 얻고, 1을 리턴한다.
• 첫 번째 호출한 fibonacci(1)은 1을 출력하고, 1을 리턴한다.
• fibonacci(3)은 fibonacci(2)와 fibonacci(1)의 결과를 얻고, 2를 리턴한다.

1은 2번 출력되고, 0은 1번 출력된다. N이 주어졌을 때, fibonacci(N)을 호출했을 때, 0과 1이 각각 몇 번 출력되는지 구하는 프로그램을 작성하시오.

입력

첫째 줄에 테스트 케이스의 개수 T가 주어진다.

각 테스트 케이스는 한 줄로 이루어져 있고, N이 주어진다. N은 40보다 작거나 같은 자연수 또는 0이다.

 

문제 풀이

이 문제는 재귀함수로 구현한 피보나치 함수에서 fibonacci(0), fibonacci(1)이 몇 번씩 실행되는지를 알아보는 문제입니다.

뭔가 규칙성이 있지 않을까 해서 직접 답을 구해봤습니다.

 

N = 0 -> 1 0

N = 1 -> 0 1

N = 2 -> 1 1

N = 3 -> 2 2

N = 4 -> 3 3

 

저는 여기까지 하고 규칙성을 발견했습니다!

바로 N이 0,1일 때를 제외하곤 지금 답은 그 전의 2개의 답 들을 더한 값이라는 것입니다.

문제에서 N = 40일때까지만 구하면 되므로 나올 수 있는 모든 경우를 구한 뒤 답을 출력하는 방법을 선택했습니다.

소스 코드

func solution(){
    let t = Int(String(readLine()!))!
    var test: [Int] = []
    
    for _ in 0..<t {
        test.append(Int(String(readLine()!))!)
    }
    
    var result: [(Int,Int)] = [(Int,Int)](repeating: (0,0), count: 41)
    result[0] = (1,0)
    result[1] = (0,1)
    
    for i in 2..<result.count{
        result[i] = (result[i-1].0 + result[i-2].0, result[i-1].1 + result[i-2].1)
    }
    
    for num in test {
        print("\(result[num].0) \(result[num].1)")
    }
}

solution()