피보나치 수는 F(0) = 0, F(1) = 1일 때, 1 이상의 n에 대하여 F(n) = F(n-1) + F(n-2) 가 적용되는 수 입니다.
예를들어
F(2) = F(0) + F(1) = 0 + 1 = 1
F(3) = F(1) + F(2) = 1 + 1 = 2
F(4) = F(2) + F(3) = 1 + 2 = 3
F(5) = F(3) + F(4) = 2 + 3 = 5
와 같이 이어집니다.
2 이상의 n이 입력되었을 때, n번째 피보나치 수를 1234567으로 나눈 나머지를 리턴하는 함수, solution을 완성해 주세요.
제한 조건
n은 2 이상 100,000 이하인 자연수입니다.
입출력 예
오류코드
위에 공식이 나와 있듯이 n이 주어졌을때 F(n) = F(n-1) + F(n-2)이다
재귀를 사용하면 아래 1차코드에 나와 있는것 처럼 쉽게 되나 해당 부분은 n이 작은 수면 상관이 없으나 n이 커지면 그만큼 재귀를 많이 하게 되어 런타임 에러가 발생
2차는 그런 재귀 대신 반복문을 사용하여 런타임 에러를 처리하였으나 이또한 int의 범위를 벗어나는 오버플로우가 발생
#1차
def solution(n):
if n <= 1 : return n
return solution(n-1) + solution(n-2)
#2차
def solution(n):
answer = 0
# 0 1 1 2 3 5 8 13
temp1, temp2 = 0,0
for i in range(1,n+1):
if i == 1 : temp1 = 1
if i == 2 : temp2 = 1
answer = temp1 + temp2
temp1, temp2 = temp2, answer
return answer
수정코드
오버플로우가 발생하지 않도록 숫자의 길이를 제한하여 나머지 계산을 통하여 값이 들어가 수정
def solution(n):
answer = 0
MOD = 1234567
if n == 1: return 0
elif n == 2: return 1
else:
a, b = 1, 1
for _ in range(n - 2):
a, b = b, (a + b) % MOD
answer = b
return answer
