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

백준 1003번 파이썬 피보나치 함수 문제 풀이입니다.

백준 1003번 파이썬 피보나치 함수 문제 풀이

문제 해설

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

1. 풀이 과정 (틀림)

def fibo(n):
  global zero_count
  global one_count
  if n == 0:
    zero_count += 1
    return 0
  elif n == 1:
    one_count += 1
    return 1
  else:
    return fibo(n-1) + fibo(n-2)

N = int(input())

for i in range(N):
  n = int(input())
  zero_count = 0
  one_count = 0
  fibo(n)
  print(zero_count, one_count)

일반적인 다이나믹 프로그래밍 재귀 방식으로 피보나치 수열을 구하는 코드를 짰다. 0과 1을 호출할 때마다 카운트를 올려주는 방식을 사용했는데, 정답을 제대로 출력하지만 시간초과 오류가 발생했다.

 

2. 정답 코드 

def calc(n):
  zero = [1, 0, 1]
  one = [0, 1, 1]
  if len(zero) <= n:
    for i in range(len(zero), n+1):
      zero.append(zero[i-2]+zero[i-1])
      one.append(one[i-2]+one[i-1])
  return zero[n], one[n]

N = int(input())

for i in range(N):
  n = int(input())
  a, b = calc(n)
  print(a, b)

피보나치 수열의 0과 1이 호출되는 횟수 또한 피보나치 수열을 따른다. 밑의 테이블을 보면 무슨 얘기인지 알 수 있다.

N	0	1	2	3	4	5	6
zero	1	0	1	1	2	3	5
one	0	1	1	2	3	5	8

이 알고리즘에 따라서 피보나치 수열을 직접 구하지 않고, 0과 1의 호출횟수를 별도로 반복문 형식을 만들어서 n일때의 값을 구해주면 된다.

 

문제를 풀면서 든 의문점은 왜 위의 풀이코드는 시간초과가 나는데 밑의 코드는 시간초과가 안나는지이다. 재귀함수와 반복문의 알고리즘 차이 때문인지, 아니면 0과 1의 호출횟수 더해주는 연산이 추가돼서 성능에 영향을 미쳐서 그러는지 잘 모르겠다. 밑의 풀이법은 리스트에 append해주는 연산이 들어가니까 아마 비슷할 것 같은데..

 

맺으며

다이나믹 프로그래밍 문제는 구조는 거의 대부분 동일하다. 가장 어려운 점은 DP 문제임을 알아차리는 것과, 점화식을 떠올리는 것이다. 특히나 다른 문제에 비해 수학적인 직관이 많이 필요로 해서 까다로운 유형중 하나인 것 같다.