[Algorithm] 백준 1003번 : 피보나치 함수 (C++)

문제 링크 : https://www.acmicpc.net/problem/1003

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이다.

[출력]

각 테스트 케이스마다 0이 출력되는 횟수와 1이 출력되는 횟수를 공백으로 구분해서 출력한다.

[알고리즘 분류]

• 다이다믹 프로그래밍

---

[해설]

이 문제에서는 보기로 피보나치를 구현한 로직을 보여주고 있다. 물론, 제시된 보기와 같이 재귀함수로 피보나치 수를 구할 수는 있지만, 문제에서 요구하는 시간 제한인 0.25초를 만족할 수는 없다. (문제에서 최대 값으로 입력될 수 있는 40과 같은 수가 입력되면 많은 재귀가 발생하여 시간초과가 일어나기 때문이다.)
따라서, 시간 제한 요구를 만족하기 위해서는 피보나치 수들이 출력하는 0과 1의 개수 사이의 규칙성을 찾고 이를 미리 저장해 수가 입력되면 저장된 인덱스를 찾아 출력하는 방식으로 해결해야한다.
모든 수들의 0, 1이 출력되는 개수를 찾기 위해, 문제에서 보기로 주어진 로직을 사용해 각 피보나치 수들의 0과 1의 개수를 계산해본 결과 다음과 같은 결과가 나왔다.

숫자 = 0 에서 0이 출력된 횟수: 1, 1이 출력된 횟수: 0
숫자 = 1 에서 0이 출력된 횟수: 0, 1이 출력된 횟수: 1
숫자 = 2 에서 0이 출력된 횟수: 1, 1이 출력된 횟수: 1
숫자 = 3 에서 0이 출력된 횟수: 1, 1이 출력된 횟수: 2
숫자 = 4 에서 0이 출력된 횟수: 2, 1이 출력된 횟수: 3
숫자 = 5 에서 0이 출력된 횟수: 3, 1이 출력된 횟수: 5
숫자 = 6 에서 0이 출력된 횟수: 5, 1이 출력된 횟수: 8
숫자 = 7 에서 0이 출력된 횟수: 8, 1이 출력된 횟수: 13
숫자 = 8 에서 0이 출력된 횟수: 13, 1이 출력된 횟수: 21
숫자 = 9 에서 0이 출력된 횟수: 21, 1이 출력된 횟수: 34
숫자 = 10 에서 0이 출력된 횟수: 34, 1이 출력된 횟수: 55

각 숫자들에서 0과 1이 출력된 횟수를 보면 0을 제외하고는 모든 수의 0과 1의 출력 횟수에서 피보나치 수열의 규칙이 적용되는 것을 볼 수 있다.
이를 이용해 아래와 같은 로직을 구성할 수 있다.

[정답 코드]

#include <ios>
int T,N,zero[41]={1,0,1,1},one[41]={0,1,1,2};

int main() {
  scanf("%d",&T);
  for(int i=4;i<41;i++){
    zero[i]=zero[i-2]+zero[i-1];
    one[i]=one[i-2]+one[i-1];
  }
  while(T--){
    scanf("%d",&N);
    printf("%d %d\n",zero[N],one[N]);
  }
}

[결과]