[백준 1003] 피보나치 함수 / 파이썬

N번째 피보나치를 구하는 코드에서 0과 1이 몇 번 출력되는지 구하는 프로그램을 작성하라고 한다.

아는게 많이 없어서 그런가 시한 제한이 있는 문제는 감이 잘 오지 않는다.
count0, count1를 전역변수로 선언하여 카운팅한다.
fibo함수에서는 n이 0, 1이면 count0, count1을 증가시키고 0, 1리턴한다. 이외의 숫자라면 다음 계산을 진행한다.

import sys
input = sys.stdin.readline

def fibo(n):
    global count0, count1
    if n == 0:
        count0 += 1
        return 0
    elif n == 1:
        count1 += 1
        return 1
    else:
        return fibo(n - 1) + fibo(n - 2)
    
for _ in range(int(input())):
    n = int(input())
    count0, count1 = 0, 0
    fibo(n)
    print(count0, count1)

시간 오버가 나온다.
짜면서도 그럴 것 같았다.

힌트는 n이 40보다 작거나 같은 자연수 또는 0이라는 멘트다.

import sys
input = sys.stdin.readline

count0 = [0] * 41
count1 = [0] * 41

count0[0], count1[1] = 1, 1
for i in range(2, 41):
    count0[i] = count0[i - 1] + count0[i - 2]
    count1[i] = count1[i - 1] + count1[i - 2]

for _ in range(int(input())):
    n = int(input())
    print(count0[n], count1[n])

import sys
input = sys.stdin.readline

x = int(input())

count = [0] * 1000001

for i in range(2, x + 1):
    count[i] = count[i - 1] + 1
    if i % 2 == 0:
        count[i] = min(count[i], count[i // 2] + 1)
    if i % 3 == 0:
        count[i] = min(count[i], count[i // 3] + 1)
print(count[x])