{프로젝트 오일러/Project Euler} 2. 짝수 피보나치 항의 합

한국어/Hackerrank - 한국어 버전과 문제가 다를 수 있습니다. 채점은 Hackerrank를 추천합니다.

입력받은 수보다 작은 짝수인 피보나치 항의 합을 출력하는 문제

even_fibonacci = [2]
max_limit = 4*1e16
evFi1, evFi2 = 0, 2
while True:
  next_evFi = 4*evFi2 + evFi1
  if next_evFi >= max_limit:
    break
  evFi1, evFi2 = evFi2, next_evFi
  even_fibonacci.append(evFi2)
for _ in range(int(input())):
	n = int(input())
	S = filter(lambda x: x<n, even_fibonacci)
	print(sum(S))

피보나치수열은 N번 항을 F(n)이라고 할 때 F(n) = F(n-1) + F(n-2)인 수열이다.

(이전 두 항의 합이 새로운 항이 되는 숫자의 배열)

또한, 피보나치 수열은 홀수 두 개(1과 1)로 시작하기 때문에 3의 배수 항마다 짝수가 등장합니다.

(홀수, 홀수, 홀수+홀수(짝수), 홀수+짝수(홀수), 짝수+홀수(홀수), 홀수+홀수(짝수).........)

그러면 짝수 항을 구하기 위해 위의 수열 식을 전개해보도록 하겠습니다.

F(n) = F(n-1) + F(n-2)
     = F(n-2) + F(n-3) + F(n-3) + F(n-4) # F(n-1)과 F(n-2) 분해
     = 2F(n-3) + F(n-2) + F(n-4)
     = 2F(n-3) + F(n-3) + F(n-4) + F(n-5) + F(n-6) # F(n-2)와 F(n-4) 분해
     = 3F(n-3) + F(n-4) + F(n-5) + F(n-6)
     = 4F(n-3) + F(n-6) # F(n-4) + F(n-5) = F(n-3)

이때, F(n)이 짝수라면 F(n-3)과 F(n-6)도 짝수가 되기 때문에

짝수 항을 EF(n)이라고 두면 EF(n) = 4*EF(n-1)+EF(n-2)가 됩니다.

---

그러면 위의 코드를 설명하겠습니다.

먼저 첫번째 항을 0, 두번째 항을 2로 두고 항의 최댓값이 4*10^16보다 작아야 하기 때문에 최대를 4*10^16으로 둡니다.

다음 항은 전의 항*4 + 전전의 항이므로 이에 맞게 구한 후 만약 최대보다 크거나 같으면 반복문을 빠져나옵니다.

만약 최대보다 작다면 전전의 항을 전의 항으로, 전의 항을 다음 항으로 업데이트합니다. (EF(n-2) = EF(n-1), EF(n-1) = EF(n))

 그리고 이렇게 구한 새로운 항을 짝수 피보나치 항을 저장한 리스트에 넣습니다.

최대까지의 모든 짝수 피보나치 항을 구했다면 각 입력받은 수별로 그보다 작은 항들의 합을 구해야 합니다.

파이썬의 filter함수는 bool값을 반환하는 함수와 이터러블을 인자로 받아

함수가 참일 때의 값들을 모아 새로운 이터러블을 반환합니다.

그래서 n보다 작은 값들의 이터러블의 합을 sum 함수를 통해 구한 뒤 그 합을 출력하면 됩니다.

 

*참고 GeeksForGeeks의 Nth Even Fibonacci