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

1003번: 피보나치 함수

---

초반에는 그냥 단순하게 메모 사용하면 되는 게 아닌가 했는데 생각보다 삽질을 좀 많이 했다. 

처음에는 n이 0이거나 1일 때 cnt_0과 cnt_1이라는 변수를 만들어서 하나씩 값을 더하며 구하려고 했는데 메모를 사용하면 n이 몇이 되든 저 두 변수의 값은 1과 2로 고정이 된다. 

 

그래서 어떻게 해야 할까 하다가 n이 6일 경우 0과 1이 각각 몇 번 나오는지 보려고 그림을 그려봤다.

숫자 옆에 배열은 각각 0과 1의 횟수이다. 

그런데 저 숫자들을 보니 1, 1, 2, 3, 5, 8.. 피보나치 수열이었다.

 

사실 중간에 삽질이 더 생략되어 있긴 하지만 피보나치 수열이라는 것을 알게되고 코드를 아래와 같이 작성했다. 

n = int(input())
lst = [int(input()) for _ in range(n)]

def fibo(n):
  if n == 0 or n == 1:
    return n
  if memo[n - 1] == 0: 
    memo[n - 1] = fibo(n - 1)
  if memo[n - 2] == 0:
    memo[n - 2] = fibo(n - 2)
  return memo[n - 1] + memo[n - 2]

for n in lst:
  if n == 0:
    print("1 0")
  elif n == 1:
    print("0 1")
  else:
    memo = [0] * n
    cnt_1 = fibo(n)
    cnt_0 = memo[n - 1]
    print(cnt_0, cnt_1, sep=" ")

일단 fibo함수는 메모이제이션을 이용한 n번째 피보나치 수를 반환해주는 평번한 함수이다. 

 

n이 0이나 1인 경우에는 그냥 출력을 시키고 그 외의 경우에는 메모 크기를 할당해주고 피보나치 함수를 호출을 해서 메모를 피보나치 수열로 채운다. 

그리고 n번째 피보나치 수가 1의 개수이고, n - 1번째 피보나치 수가 0의 개수이기 때문에 해당 값들을 출력해주었다.