[Backjoon 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) 재귀 호출 때 마다 Count -> 시간초과

# 시간초과
def fibo(n):
    global cnt_0
    global cnt_1
    if n == 0:
        cnt_0 += 1
        return cnt_0, cnt_1
    elif n == 1:
        cnt_1 += 1
        return cnt_0, cnt_1
    else:
        return fibo(n-1) + fibo(n-2)

n = int(input())
for i in range(n):
    num = int(input())
    cnt_0, cnt_1 = 0, 0
    fibo(num)
    print(cnt_0, cnt_1)

fibo(3) -> fibo(2), fibo(1)

fibo(2) -> fibo(1), fibo(0)과 같이 계속 피보나치 함수를 호출하다 보니 시간 초과가 발생.

 

2) 정답

점화식

fibo(n)을 n에서의 0의 횟수, 1의 횟수를 찾아주는 함수라고 하면 

fibo(2)에서 0이 등장하는 횟수는 fibo(1)에서 0이 등장하는 횟수 + fibo(0)에서 0이 등장하는 횟수

fibo(2)에서 1이 등장하는 횟수는 fibo(1)에서 1이 등장하는 횟수 + fibo(0)에서 1이 등장하는 횟수로 생각할 수 있다.

이를 점화식으로 표현하면 count[i] = count[i-1] + count[i-2]와 같으며 아래와 같이 구현할 수 있다.

n = int(input())

d_0 = [1, 0]
d_1 = [0, 1]

for i in range(2, 41):
    d_0.append(d_0[i-1] + d_0[i-2]) # zero
    d_1.append(d_1[i-1] + d_1[i-2]) # one
    
for j in range(n):
    num = int(input())
    print(d_0[num], d_1[num])