[python] 피보나치 수

문제

피보나치 수열에 포함되는 수를 피보나치 수라고 한다. 피보나치 수열은 첫째 항과 둘째 항이 1이고, 그 뒤의 모든 항은 바로 앞 두 항의 합으로 정의되는 수열이다. Fi를 i번째 피보나치 수라고 했을 때, 피보나치 수열을 수식으로 정의하면 아래와 같다.

양의 정수 K가 주어질 때, Fk의 값을 구해보자. 단, 값이 매우 클 수 있으니 이를 1,000,000,007로 나눈 나머지를 대신 출력한다.

 

 

입력

첫째 줄에 양의 정수 K가 주어진다.

• 1 ≤ K ≤ 100,000

 

import sys
input = sys.stdin.readline

k = int(input())
result = [1, 1]

for i in range(2, k):
	result[0], result[1] = result[1], result[0]
	result[1] = result[0] + result[1]
	
print(result[1] % 1000000007)

처음 두 개의 값은 정해져 있으니 먼저 설정한 후 값을 하나하나 변경하며 풀이를 했다.

 

 

좀 더 파이썬 방식으로 풀면 더 간단해진다.

n = int(input())
f = [1, 1]
for i in range(100000):
    f.append((f[-1] + f[-2]) % 1000000007)
print(f[n - 1])

 

 

 

※출처

https://multicampus-kdt.goorm.io/lecture/38996/멀티잇-코딩테스트-러닝클래스-python-6월반