[백준 알고리즘: python 3] #1003 - 피보나치 함수

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

 

1003번 문제에는 피보나치 함수가 소개되어 있고, 문제에 대한 설명을 아래와 같이 해두었습니다.

처음에 드는 생각은, 아 그럼 저 코드를 python으로 똑같이 옮긴 다음에 전역 변수로 count0 와 count1 을 선언한 뒤 함수 내에 n == 0을 잡는 if 문이 실행이 되면 count0에 1을 더하고 n == 1의 경우에는 count1에 1을 더해서 출력하면 되지 않을까? 쉽네! 였습니다. 가령, 다음과 같이 말이죠.

count0 = 0
count1 = 0

def fibonacci(n):
    global count0
    global count1
    
    if n == 0:
        print("0")
        count0 += 1
        return 0
    elif n == 1:
        print("1")
        count1 += 1
        return 1
    else:
        return fibonacci(n-1) + fibonacci(n-2)

Hint!

아쉽게도 위의 코드는 시간초과 가 났습니다. 알고보니 시간제한이 0.25초 이더군요. 재귀함수이기 때문에 N이 클수록 시간이 기하급수적으로 커질거라고 생각을 했습니다. 컴공과생은 아니라 그런지 재귀함수가 일으킨 시간초과 문제를 어떻게 해야할 지 막막하여 고민을 해보다가, 제시해준 문제대로 N을 10까지 손으로 풀어봤습니다.

 

N	output
0	1 0
1	0 1
2	1 1
3	1 2
4	2 3
5	3 5
6	5 8
7	8 13
8	13 21
9	21 34
10	34 55

 

아.. 그런거군요 오른쪽에 보이는 숫자들은 모두 피보나치 수열 (1, 1, 2, 3, 5 ...) 에 존재하는 숫자들입니다. 조금 더 자세히 살펴보면 Output의 규칙은 "{n-1번째 피보나치 수} {n번째 피보나치 수}" 라고 추측해볼 수 있었습니다. 하지만, 이 사실을 안다고 해도 N번째 출력값을 찾아야하는 피보나치 함수 코드는 변함이 없을 것이라 생각을 했고, 코드를 바꿔야겠다는 생각을 했습니다. 그러던 중,

 

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

라는 입력 조건이 있었음을 확인할 수 있었는데요, 그러면 먼저 피보나치 함수를 N이 40일 때까지 미리 계산하여(재귀함수를 사용하지 않아도 될테니까요.) list 형태로 할당해두고 "{n-1번째 피보나치 수} {n번째 피보나치 수}" 를 바로 출력해내면 되지 않을까 생각했습니다. 이러한 생각으로 아래와 같은 코드를 작성하여 풀이했습니다.

 

fibonacci = []
for i in range(41):
    if i == 0: fibonacci.append(0)
    elif i == 1: fibonacci.append(1)
    else: fibonacci.append(fibonacci[i-2] + fibonacci[i-1])

num = int(input())
results = []

for j in range(num):
    n = int(input())
    # n이 0과 1일 때는 따로 정의해주어야 문제의 조건과 맞습니다.
    if n == 0: results.append([1, 0])
    elif n == 1: results.append([0, 1])
    else: results.append([fibonacci[n-1], fibonacci[n]])

for result in results:
    print(result[0], result[1])