[백준 10826: 피보나치 수 4] 파이썬 풀이

10826번: 피보나치 수 4

---

문제

피보나치 수는 0과 1로 시작한다. 0번째 피보나치 수는 0이고, 1번째 피보나치 수는 1이다. 그 다음 2번째 부터는 바로 앞 두 피보나치 수의 합이 된다.

이를 식으로 써보면 Fn = Fn-1 + Fn-2 (n ≥ 2)가 된다.

n=17일때 까지 피보나치 수를 써보면 다음과 같다.

0, 1, 1, 2, 3, 5, 8, 13, 21, 34, 55, 89, 144, 233, 377, 610, 987, 1597

n이 주어졌을 때, n번째 피보나치 수를 구하는 프로그램을 작성하시오.

 

입력

첫째 줄에 n이 주어진다. n은 10,000보다 작거나 같은 자연수 또는 0이다.

 

출력

첫째 줄에 n번째 피보나치 수를 출력한다.

 

---

 풀이

import sys
input = sys.stdin.readline

n = int(input()) 

# 초기값 저장
n1 = 0
n2 = 1

for _ in range(n-1): #반복문을 이용한 재귀
  n3 = n1 + n2 # n1과 n2를 더해서 n3에 저장하고 
  n1 = n2 #n1과 n2를 다시 세팅
  n2 = n3


if(n==0): # n이 0일 경우와 1일 경우는 각각 0과 1을 출력하도록 작성
  print(0)
elif(n==1):
  print(1)
else:
  print(n2)

 

• 반복문을 이용한 재귀 구현
• n만큼 반복하면서 n1과 n2를 더해서 n3에 저장하고, n1과 n2를 새로운 값으로 세팅
• 이렇게 반복문으로 저장한 값을 출력해주면 n이 0과 1일때는 값이 정상적으로 출력되지 않아서, 0과 1만 값을 지정해주었습니다.

---

💡 Challenge

import sys
input = sys.stdin.readline

n = int(input()) 
li = [0, 1] # 결과를 저장할 리스트 li, 초기 더할 값인 0과 1을 미리 저장

def fibonacci(num1, num2): # 피보나치 함수 정의
  num3 = num1 + num2
  li.append(num3) # 피보나치 수열의 결과를 li에 저장
  
  num1 = num2
  num2 = num3
  
  if(len(li) > n+1): # li에 저장한 결과가 n+1 이상이면 재귀를 종료
    return -1
	
  fibonacci(num1, num2) # 재귀 호출

fibonacci(0,1)
print(li[n])

 

피보나치면 당연히 재귀로 작성하면 될 줄 알고

재귀함수를 호출하는 코드를 작성했습니다.

 

 

풀이 방법

• fibonacci라는 함수를 정의해서 num1과 num2를 저장해서 값을 바꾸도록 구현
• li에 결과를 저장
• li에 저장한 결과가 n+1 이상이면 재귀를 종료하고,
• 아니면 다시 재귀함수 호출

---

답은 맞게 나오는 것 같았는데 제출하니 런타임 에러가 발생했습니다.

 

 

 

런타임 에러 (RecursionError)

런타임 에러 (RecursionError)

 

재귀 깊이가 너무 깊을 때 나타나는 에러라고 해서 반복문으로 고쳐서 다시 풀었습니다.