BOJ 1003: 피보나치 함수- 파이썬(Python)

https://www.acmicpc.net/problem/1003

 

<접근 방법>

피보나치수열에서 0과 1이 각각 몇 번 출력되는지를 계산하는 문제이다.

 

n = 4일 때의 상황에서 아래의 배열을 생각해 보자.

N	0	1	2	3	4
0의 개수	1	0	??	??	??
1의 개수	0	1	??	??	??

 

우선 0과 1은 자명하다. 0은 $(0의 개수, 1의 개수) = (1, 0)$이고, 1은 $(0의 개수, 1의 개수) = (0, 1)$이 될 것이다.

이제 2 이상일 때에는 어떻게 될지 살펴보자.

 

피보나치 함수 계산식은 $fibonacci(N) = fibonacci(N - 1) + fibonacci(N - 2)$로 계산하므로, 이를 0과 1에서의 관점으로 변형해 보자. 그러면 아래의 점화식을 구성할 수 있다.

(N일 때의 0의 개수) = (N - 1일 때의 0의 개수) + (N - 2일 때의 0의 개수)
(N일 때의 1의 개수) = (N - 1일 때의 1의 개수) + (N - 2일 때의 1의 개수)

 

위의 점화식을 이용하면 0과 1의 개수를 $O(N)$의 시간복잡도로 계산할 수 있다.

 

아래 표는 위의 점화식으로 계산한 $N = 4$일 때의 결과이다.

N	0	1	2	3	4
0의 개수	1	0	1	1	2
1의 개수	0	1	1	2	3

<소스 코드>

위의 코드를 이용한 전체 소스 코드 구현 결과이다.

 

import sys
import time
start = time.time()

def fibo_count(n):
    fib = [(1, 0), (0, 1)]
    
    for i in range(2, n + 1):
        fib.append((fib[i - 1][0] + fib[i-2][0], fib[i - 1][1] + fib[i - 2][1]))
        
    return fib[n]

case = int(sys.stdin.readline())
for _ in range(case):
    n = int(sys.stdin.readline())
    print(*(fibo_count(n)))