[백준 24416번] 알고리즘 수업 - 피보나치 수 1

n = int(input())

dp = [0]*41

count_r = 0
count_d = 0

def fib_recursive(n): # 일반적인 재귀함수 피보나치 수열 계산
  global count_r
  
  if n==1 or n==2:
    count_r += 1
    return 1
  else:
    return fib_recursive(n-1) + fib_recursive(n-2)


def fib_dynamic(n): # 동적계획법을 사용한 피보나치 수열 계산

  global count_d
  
  if n==1 or n==2:
    if dp[n] == 0:
      dp[n] = 1
    return dp[n]
  
  else:
    if dp[n] != 0:
      return dp[n]
    else:
      count_d += 1
      dp[n] = fib_dynamic(n-1) + fib_dynamic(n-2)
      return dp[n]

fib_dynamic(n)
fib_recursive(n)
print(count_r,count_d)

위 코드는 처음 문제를 풀이할 때 작성한 코드인데, Python3으로 실행시켰을 때 시간초과가 뜨길래 한동안 헤맸었는데  pypy3로 돌려보니 성공했다 ^^ ...

 

하지만 pypy3로 돌리기 전에 DP 만으로 어떻게 해결할 수 있을지와 좀 더 코드를 깔끔하게 작성하기 위해 다른 분의 코드를 참고하였었다.

 

먼저 새로 알게 된 사실은 n = 1인 경우와 n = 2인 경우의 개수는 곧 피보나치 수열의 값과 동일하다는 것이다.

ex) f(5) = 5 = f(1)과 f(2)의 호출 횟수

 

처음에는 왜 이렇게 되는지 이해가 가지 않았는데, 결국 DP로 풀이할 때 작은 문제(Sub Problem)인 f(1)과 f(2)의 값들이 합쳐지면서 큰 문제에 대한 정답이 나오기 때문에 당연하게도 f(n)의 결과와 f(1)과 f(2)의 개수는 동일할 수 밖에 없었다.

 

따라서 DP로만 풀이한 코드는 다음과 같다.

n = int(input())

dp = [0]*41
count = 0

def fib_dynamic(n):
  global count
  
  if n == 1 or n == 2:
    return 1

  if dp[n] != 0:
    return dp[n]

  count += 1
  dp[n] = fib_dynamic(n-1) + fib_dynamic(n-2)

  return dp[n]

print(fib_dynamic(n),count)

이번 문제를 풀면서 느낀 점은 if문에서 return을 해준다면 굳이 뒤에 else를 줄줄이 해줄 필요가 없기 때문에 코드를 더 깔끔하게 작성할 수 있다는 것이다 :)