[Baekjoon]백준 1003 피보나치 함수(실버 3) - Python

문제설명 1

문제설명 2

문제를 살펴보면 피보나치를 활용하였는데, 그 과정속에서 0과 1이 총 몇번 출력되었는지 출력하는 문제이다

처음에는 문제에서 제시한 C++ 함수를 활용하여 코드를 작성하였는데, 시간이 0.25초로 짧기 때문에

해당 코드를 제출하면 시간초과가 발생한다

import sys
input = sys.stdin.readline

def fibonacci(num):
    global zero_count
    global one_count
    if num == 0:
        zero_count += 1
        return 0
    elif num == 1:
        one_count += 1
        return 1
    else:
        return fibonacci(num-1) + fibonacci(num-2)
        
case_num = int(input())
for _ in range(case_num):
    zero_count, one_count = 0, 0
    N = int(input())
    fibonacci(N)
    print(zero_count, one_count)

시간 초과를 보자말자 떠오른 생각이 dp를 활용하여 풀이하면 시간안에 해결가능할 것이라는 생각이 들었다

그래서 0과 1의 개수를 저장하는 리스트를 각각 만들어주었다

또한 -1로 초기화하였기때문에 fibonacci함수 내에서 -1인지 확인하는 로직을 추가하여 중복으로

연산하는 것을 방지해주면 된다 피보나치의 경우 이전 값(i-1)과 그 이전 값(i-2)을 더해주는 것이기 때문에

zero_count, one_count에도 동일하게 동작하도록 작성해주면 코드가 완성된다

import sys
input = sys.stdin.readline

def fibonacci(num):
    for i in range(2, num+1):
        if zero_count[i] == -1:
            zero_count[i] = zero_count[i-1] + zero_count[i-2]
            one_count[i] = one_count[i-1] + one_count[i-2]
        
case_num = int(input())
zero_count = [1, 0] + [-1] * 39
one_count = [0, 1] + [-1] * 39
for _ in range(case_num):
    N = int(input())
    fibonacci(N)
    print(zero_count[N], one_count[N])