피보나치 함수

풀이

처음엔 문제에서 보이는 소스코드르 이용해서 python화 하고, 바로 그곳에 0이 출력된 개수와 1이 출력된 개수를 저장하는 변수를 이용해서 풀이했다.

def fibonacci(n):
    global number0
    global number1
    if n == 0:
        number0 += 1
        return 0
    elif n == 1:
        number1 += 1
        return 1
    else:
        return fibonacci(n-1) + fibonacci(n-2)

T = int(input())
for testcase in range(T):
    # 0이 출력되는 횟수와 1이 출력되는 횟수
    N = int(input())
    number0 = 0
    number1 = 0
    fibonacci(N)
    print(number0, number1)

테스트 케이스에선 문제가 없었다. 실제 문제에서도 답은 다 맞았을 것이다. 하지만 문제를 푸는데 있어서 시간 초과가 발생했다. 아무래도 fibonacci() 함수를 바닥까지 찍어두고 시작하니 그런가 보다.

그래서 다른 생각을 해보았다.
혹시 출력값에서 내가 얻어낼 수 있는 무언가가 있지는 않을까? 그래서 N을 0~19까지 넣었을 때 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
9
#21, 34
10
#34, 55
11
#55, 89
12
#89, 144
13
#144, 233
14
#233, 377
15
#377, 610
16
#610, 987
17
#987, 1597
18
#1597, 2584
19
#2584, 4181

이 출력값을 보면 바로 눈치챌 수 있듯이 N이 2 이상일 경우는 0이 출력된 횟수는 이전 겂 N-1에서 1이 출력된 횟수와 같았다.
그러면 1이 출력된 횟수는 어떠하냐면, 이전 값 N-1에서 0이 출력된 횟수와 1이 출력된 횟수를 더한 값이다.

이를 이용해서 해결하는 함수를 생성하고, 코드를 아래처럼 작성했다.

def solution(N):
    if N == 0:
        return [1,0]
    elif N == 1:
        return [0,1]
    else:
        answer = [0,1]
        for _ in range(N-1):
            tmp0 = answer[1]
            tmp1 = answer[0]+answer[1]
            answer = [tmp0, tmp1] 
        return answer
T = int(input())
for testcase in range(T):
    # 0이 출력되는 횟수와 1이 출력되는 횟수
    N = int(input())
    a = solution(N)
    print(f'{a[0]} {a[1]}')

이렇게 하니 시간 초과 없이 문제가 제대로 풀렸다. 굳