[백준 1003번] 피보나치 함수 - python

문제 링크

https://www.acmicpc.net/problem/1003

1003번: 피보나치 함수

풀이

- dp 문제 

- N일 때 0이 등장하는 개수를 저장하는 배열 : zero

- N일 때 1이 등장하는 개수를 저장하는 배열 : one

- 점화식

  zero[i] = zero[i-1] + zero[i-2]
  one[i] = one[i-1] + one[i-2]

1. N의 범위가 0부터 40이므로 각 배열을 [0] * 41 로 초기화

2. 3부터 41까지 one과 zero 값 구하기

3. 주어진 숫자에 해당하는 값 출력 

n = int(input())

zero = [0] * 41
zero[0] = 1
zero[1] = 0
zero[2] = 1

one = [0] * 41
one[0] = 0
one[1] = 1
one[2] = 1

for i in range(3, 41):
  zero[i] = zero[i-1] + zero[i-2]
  one[i] = one[i-1] + one[i-2]

for _ in range(n):
  num = int(input())
  print(zero[num], end =" ")
  print(one[num])