[알고리즘] 동적 계획법(Dynamic Programming) - 백준 1003번 피보나치 함수

정답 코드

def fibonacci(n):
  zero_count = [1, 0]
  one_count = [0, 1]

  for i in range(2, n+1):
    zero_count.append(zero_count[i-1] + zero_count[i-2])
    one_count.append(one_count[i-1] + one_count[i-2])

  return zero_count, one_count

N = int(input())
for _ in range(N):
  k = int(input())
  zero_count, one_count = fibonacci(k)
  print(zero_count[k], one_count[k])

풀이과정

fibonacci(0) = 0 출력(1) + 1 출력(0) = 1
fibonacci(1) = 0 출력(0) + 1 출력(1) = 1
fibonacci(2) = 0 출력(1) + 1 출력(1) = 2
fibonacci(3) = 0 출력(1) + 1 출력(2) = 3
fibonacci(4) = 0 출력(2) + 1 출력(3) = 5

n번째 0 출력 횟수: ( n-1번째 0 출력 횟수 ) + ( n-2번째 0 출력 횟수 )
n번째 1 출력 횟수: ( n-1번째 1 출력 횟수 ) + ( n-2번째 1 출력 횟수 )

잘못된 코드

zero_count, one_count = 0, 0

def fibonacci(n):
  cache = [-1 for _ in range(n+1)]
  
  def iterate(n):
    global zero_count, one_count
    
    if n < 2:
      if n == 0:
        zero_count += 1
      elif n == 1:
        one_count += 1
      return n

    if cache[n] != -1:
      return cache[n]
    
    cache[n] = iterate(n-1) + iterate(n-2)
    return cache[n]
  
  return iterate(n)

N = int(input())
for _ in range(N):
  zero_count, one_count = 0, 0
  fibonacci(int(input()))
  print(zero_count, one_count)