[백준] 1003번: 피보나치 함수 - [Python/파이썬]

 

문제

1003번: 피보나치 함수

 

문제 정의

첫째 줄에 테스트 케이스의 개수 T가 주어진다.

각 테스트 케이스는 한 줄로 이루어져 있고, N이 주어진다. N은 40보다 작거나 같은 자연수 또는 0이다.

이때, 주어진 각 N에 대해 문제에서 주어진 fibonacci 함수를 적용했을 때, 0이 출력되는 횟수와 1이 출력되는 횟수를 공백으로 구분해서 출력합니다.

 

코드

import sys
input=sys.stdin.readline
count0=[1,0,1]
count1=[0,1,1]
def fibonacci(n):
  if n>=len(count0):
    for i in range(len(count0), n+1):
      count0.append(count0[i-1]+count0[i-2])
      count1.append(count1[i-1]+count1[i-2])

T=int(input())
for i in range(T):
  num=int(input())
  fibonacci(num)
  print(count0[num], count1[num])

 

문제 해결

0의 개수와 1의 개수를 저장할 리스트를 선언

dp의 개념을 활용하여 피보나치 문제를 해결한다

-> 배열을 만들어서 값을 저장하는 이유는 이미 구한 숫자를 또 다시 구하는 일이 없도록 하여 단축시키기 위함이다

 

fibonacci(n)= fibonacci(n-1) + fibonacci(n-2)를 적용하여

피보나치 n에서의 0,1의 호출 횟수 = 피보나치 n-1 에서의 0,1의 호출 횟수 + 피보나치 n-2에서의 0,1의 호출 횟수

를 활용하여 새로운 값을 리스트에 추가