[다이나믹 프로그래밍] 1003번 - 피보나치 함수

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

(한줄평) 피보나치 수를 구하는 문제에서 약간 변형된 문제로 피보나치 수열 문제 풀 때 한번쯤 다시 풀어보면 좋을 것 같은 문제!

40이하의 자연수/0 이 n으로 주어질 때, fibo(n)이 호출되었을 때 fibo(0)과 fibo(1)이 호출되는 횟수를 구하는 문제다. 재귀 혹은 반복문을 이용하여 풀 수있고 두 방식 모두 메모리나 시간 측면에서는 동일하니 편한 방식으로 풀면 될 것 같다. 

(풀이1) 재귀 이용(내 풀이)

풀이 시간: 20분 이내

1) 문제 해결 아이디어

재귀를 이용한 풀이 방식이다. n번째 피보나치 수를 저장하는 dp 테이블(d)에 기존에는 피보나치 수 1개 값만 저장했다면 이 문제에서는 [피보나치 수, 0 호출 횟수, 1 호출 횟수] 3개 값을 저장한다.

 

<점화식>

fibo(n) = fibo(n - 1) + fibo(n - 2) 이므로 fibo(n)의 fibo(0), fibo(1)의 호출 횟수는 다음과 같다.

fibo(n)의 fibo(0) 호출 횟수 = fibo(n - 1)의 fibo(0) 호출 횟수 + fibo(n -2)의 fibo(0)의 호출 횟수

fibo(n)의 fibo(1) 호출 횟수 = fibo(n - 1)의 fibo(1) 호출 횟수 + fibo(n -2)의 fibo(1)의 호출 횟수

 

2) 소스코드

def fibo(n):
  if n == 0:    
    return 0
  elif n == 1: 
    return 1
  else:
    # 기록된 값이 없으면 계산
    if d[n][0] == 0:  
      d[n][0] = fibo(n - 1) + fibo(n - 2)  # n번째 피보나치 수
      d[n][1] = d[n - 1][1] + d[n - 2][1]  # n번째 피보나치 수의 0 호출 횟수
      d[n][2] = d[n - 1][2] + d[n - 2][2]  # n번째 피보나치 수의 1 호출 횟수
    return d[n][0]

t = int(input())  # 테스트 케이스 수
for _ in range(t):
  n = int(input())  # 
  d = [[0, 0, 0] for _ in range(41)]  # 40이하의 자연수/0
  d[0] = [0, 1, 0]
  d[1] = [1, 0, 1]
  
  fibo(n)
  print(d[n][1], d[n][2])  # n번째 피보나치수 0, 1 호출 횟수

 

(풀이2) 반복문 이용

풀이 시간: 20분 이내

1) 문제 해결 아이디어

반목문을 이용한 풀이 방식이다. 아이디어 자체는 동일하나 사실 피보나치 수는 굳이 저장을 하지 않고 0 호출 횟수, 1 호출 횟수 2개의 값만 저장을 해도 풀 수 있는 문제다. 이 문제에서는 0 호출 횟수, 1 호출 횟수를 저장하는 1차원 리스트 2개를 생성하고 값을 저장한다.

 

2) 소스코드

 

 

[참고] https://jiwon-coding.tistory.com/28

[백준] 1003번 피보나치 함수 / 파이썬(python)