[Baekjoon] # 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이 각각 몇 번 출력되는지 구하는 프로그램을 작성하시오.

예제

• 입력 1

  3
  0
  1
  3
  

• 출력 1

  1 0
  0 1
  1 2
  

• 입력 2

  2
  6
  22
  

• 출력 2

  5 8
  10946 17711
  

  ---

Solution

def get_inputs():
    import sys

    input_data = sys.stdin.read()
    inputs = input_data.splitlines()

    item_count = int(inputs[0])
    data = map(int, inputs[1:])

    return item_count, data


def solution(n):
    """
    [0이 호출되는 횟수, 1이 호출되는 횟수]
    """
    if n == 0:
        return "1 0"
    elif n == 1:
        return "0 1"

    result = [[1, 0], [0, 1]]

    for _ in range(2, n + 1):
        result.append([result[-1][0] + result[-2][0], result[-1][1] + result[-2][1]])

    return " ".join(map(str, result[-1]))


def main():
    _, inputs = get_inputs()

    result = [solution(n) for n in inputs]

    print(*result, sep="\n", end="")


if __name__ == "__main__":
    main()

---

해결 방법

---

피보나치 수열

• 피보나치 수열을 구하는 방법을 생각해보면, $(n - 2)$ 번째 항과 $(n - 1)$ 번째 항을 더해서 $n$ 번째 항을 구한다.

• 문제 또한 $(n - 2)$ 번째에 호출한 횟수와 $(n - 1)$ 번째에 호출한 횟수를 더하여 구한다.

• 피보나치 수열과 같은 방법으로 문제를 해결한다.

---

의사 코드

1. 먼저 n이 0인지 확인:
   • 만약 n이 0이면, 문자열 "1 0"을 반환.
2. n이 1인지 확인:
   • 만약 n이 1이면, 문자열 "0 1"을 반환.
3. 그렇지 않으면, result라는 리스트를 [[1, 0], [0, 1]]로 초기화:
   • result[0]은 n=0일 때 0과 1의 호출 횟수를 나타냄.
   • result[1]은 n=1일 때 0과 1의 호출 횟수를 나타냄.
4. n이 2 이상인 경우, 2부터 n까지의 숫자에 대해 반복:
   • 각 반복마다, result 리스트에 새로운 값을 추가:
     • [result[-1][0] + result[-2][0], result[-1][1] + result[-2][1]]를 추가함.
     • 이는 피보나치 수열과 유사하게 이전 두 항의 값들을 더하는 방식임.
5. 반복이 끝나면, result 리스트의 마지막 요소를 문자열로 변환하여 반환:
   • 반환되는 문자열은 공백으로 구분된 0과 1의 호출 횟수임.

---

URL

• 피보나치 함수