BOJ 1003 피보나치 함수 #백준

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

시간제한 0.25초 | 메모리 128mb | 정답률 32.5%

 

<input case>

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

 

 

<Output case>

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

input example	Output example
3 0 1 3	1 0 0 1 1 2
2 6 22	5 8 10946 17711

<Idea>

Q: 피보나치 수열은 위 문제에 적힌 것처럼 재귀함수로 구현하는 것이 일반적입니다.
A: 하지만 대부분의 문제에서 피보나치 수열 같은 경우는 재귀 깊이 초과(recursion error)를 범하게 될 가능성이 높습니다.
Q. 보통은 최대 재귀 깊이를 늘려서 해결하는 방식도 존재하지만 이 방법은 단순히 굴러가게만 만들기 때문에 이 문제처럼 시간 제한이 빡빡한 문제같은 경우는 높은 확률로 시간 초과로 이어지게됩니다. 그럼 이런 경우에는 어떻게 해야 할까요? 
A. 바로 다이나믹 프로그래밍을 활용하는 방법입니다. 다이나믹 프로그래밍은 간단히 내가 반복 실행해야할 시간을 공간(메모리)에 미리 저장 시켜서 실행시간을 단축하는 방법이라 말 할 수 있습니다. 
Q. 일단 다이나믹 프로그래밍을 사용하지 않고 6의 피보나치 수를 계산한다고 가정해봅시다.

https://yeojin-dev.github.io/blog/fibonacci-number-1/

A:.그럼 이상의 그림만큼의 재귀가 이루어집니다. 보통 아무런 조치도 취하지 않은 피보나치 수열의 시간복잡도는 최대 O(N-square)이 나옵니다. 높은 확률로 재귀 깊이 초과가 발생하거나 시간이 초과되겠죠
Q.그래서 우린 다이나믹 프로그래밍을 활용합니다. 다이나믹 프로그래밍에선 특정 범위까지 한번만 계산하고 나머지는 불러다 사용하므로 시간복잡도는 O(N)이 되겠죠.
A.이번 문제도 마찬가지입니다 시간초과와 재귀 초과 문제를 해결하기 위해 다이나믹 프로그래밍을 활용해봅시다

 

런타임 에러 (RecursionError)

 

def fib(n):
  if len(data) > n:  return data[n] #시간 단축 + 재귀 초과를 해결하기 위한 추가 배열 활용
  else: temp=[0,0] #0과 1의 개수를 세어주는 임시 배열
  if n == 0: 
    temp[0] += 1
    return temp
  elif n == 1:
    temp[1] += 1
    return temp
  else: 
    data_1= fib(n-1)
    data_2=fib(n-2)
    return [data_1[0]+ data_2[0], data_1[1] + data_2[1]]
    
data=[] #각 숫자마다 0,1의 횟수를 담아두는 임시 배열
for i in range(41): data.append(fib(i)) #문제 상에서 최댓값이 40이라고 지정해뒀으므로 40까지 미리 계산해둔다.

T=int(input())
for i in range(T):
  N=int(input())
  print("{} {}".format(data[N][0],data[N][1]))