백준_1003번

1003번 피보나치 함수

 import sys
 input = sys.stdin.readline

 def fibonacci(n): #피보나치 함수 생성
         global cnt # 글로벌 구역 cnt
         if n == 0: # n이 0이면
             cnt[n] += 1 # cnt[0] 의 값 + 1
         elif n == 1: # n이 1이면
             cnt[n] += 1 # cnt[1] 의 값 + 1
         else: # n이 1보다 크면 1 작은수, 2 작은수로 다시 함수 호출
          fibonacci(n-1), fibonacci(n-2)
            
 for _ in range(int(input())):
     cnt = {0:0,1:0}
     fibonacci(int(input())) # 누적된 0, 1의 값을 출력
     print(cnt[0],cnt[1])

숫자가 커질 수록 호출 하는 수가 굉장히 커져서 시간 초과가 났다.
생각해봐도 안될 때 이용하는 아이패드...

입력값이 0~4 일 때 까지 써봤다.
0 = 1,0 그리고 1 = 0,1 일 때 2부터는 결괏값이
(입력한 숫자-1 결괏값) + (입력한 숫자-2 결괏값) 이다.
이건 문제에도 써있다 ㅎㅎ..

결괏값을 나열하니 (x,y) 기준으로
x = 이전 결괏값의 y가 되고 y = 이전 결괏값의 x+y 되는 규칙이 있었다.

for _ in range(int(input())): # 테스트 케이스 개수
    x,y = 1,0 # 0일 때 기준 0이 1번, 1이 0번
    n = int(input()) # 테스트 케이스
    if n == 0: # 입력한 수가 0이면 
        print(x, y) # 1 0 출력
    else: # 0이 아니면
        for _ in range(n): # 입력한 수 만큼 반복
            x,y = y,x+y
        print(x,y)

굳이 입력한 수가 0일 때를 따로 제외 시킬 필요가 없겠다.

for _ in range(int(input())):
    x,y = 1,0
    n = int(input())
    for _ in range(n):
        x,y = y,x+y
    print(x,y)