[백준] 1003번 문제 (피보나치 함수) 파이썬(Python) 풀이

 

첫 번째 풀이 (시간 초과)

def zero_func():
    global zero
    zero += 1
    return zero
    
def one_func():
    global one
    one += 1
    return one

def fibo(num):
    if num == 0:
        return zero_func()
    elif num == 1:
        return one_func()
    else:
        return fibo(num - 1) + fibo(num - 2)

from sys import stdin
t = int(stdin.readline())
for _ in range(t):
    zero = 0
    one = 0
    fibo(int(stdin.readline()))
    print(zero, one)

아주 쉽게 접근해서 숫자가 0인 경우와 1인 경우에 함수를 한 번씩 호출해서 전역 변수에 카운트를 해준뒤 

리턴해줬다.

하지만 재귀함수가 느린지 시간초과로 틀렸고

 

for문을 통해 접근하기로 했다.

두 번째 풀이 (성공)

t = int(input())
for i in range(t):
    n = int(input())
    zero, one = 1, 0
    for _ in range(n):
        one, zero = one + zero, one
    print(zero, one)

우선 이렇게 풀게된 흐름은..

첫 번째 풀이로 입력에 대한 출력을 미리 알아놨다.

 

입력에 대한 출력은 이렇다.

입력 n	0의 출력 수	1의 출력 수
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

 

테이블을 보면은 입력에 대해 숫자 0과 1의 출력 수는

0은 n-1의 1의 출력 수이고, 

1은 n-1의 0과 1의 출력 수의 합이라는 것을 알 수 있다. 

 

따라서 이 규칙을 코드로 작성하면 아래와 같다고 할 수 있다.

zero, one = 1, 0
for _ in range(n):
    one, zero = one + zero, one

다중 할당이 안 되는 언어는 임시 변수를 사용해서 one의 값을 잠시 할당해야겠지만

파이썬은 다중 할당이 되기 때문에 이런식으로 간결하게 해결이 가능하다.