(백준 11442) 홀수 피보나치 수의 합 (Python)

https://www.acmicpc.net/problem/11442

홀수 피보나치 수의 합 문제

홀수 피보나치 수의 합을 구하는 문제

제 생각으로 100% 해결하셨나요?
→ 오

나누기와 정복으로 피보나치 수의 합을 구하고 홀수 피보나치 수에 대한 규칙을 찾습니다.

답변 코드를 풀었습니다.

import sys
N = int(sys.stdin.readline())
x = ((1,1),(1,0))
def mult(a,b): # 행렬의 곱을 구하자
    A = ((0,0),(0,0)) # 2차원 행렬
    for i in range(2): 
        for j in range(2):
            for k in range(2):
                A(i)(j) += a(i)(k) * b(k)(j) % 1000000007 # a, b 행렬의 곱 이고 중간에 나눠도 결과는 동일
    return A  # 나누지 않고 반환하면 값이 너무 커서 처리시간 증가 

def f(x, n): #행렬을 n번 곱했을 때의 피보나치 수열 구하기
    if n == 1: 
        return x 
    else : 
        matrix = f(x,n//2) # 행렬이 n이 1이 될 때까지 재귀 반복 
        if n % 2 == 0: # 짝수면
            return mult(matrix, matrix) # 행렬끼리 곱해주기
        else: # 홀수면
            return mult(mult(matrix,matrix), x) # 행렬 곱한거에 한번 더 곱해주기

result = f(x,N)
if N % 2 == 1 :
    print((result(0)(0))% 1000000007) 
else :
    print((result(0)(1))% 1000000007)

문제 액세스 포인트

1. 먼저 피보나치 수열을 찾아봅시다. N의 크기는 1조를 넘는 매우 큰 수이기 때문에 재귀나 DP로 시간을 맞추기 어려운 구조이다.
2. 그런 다음 “분할 정복”을 사용하여 필요한 경우만 빠르게 찾을 수 있도록 구성합니다. 피보나치 수열의 경우 행렬로 나타내면 ((1,1),(1,0))의 형태로 곱셈을 반복하여 얻을 수 있는 구조를 갖는다. 이 행렬의 n번째 거듭제곱으로 나누고 정복해 봅시다.
3. 두 개의 행렬을 곱하는 행렬 곱셈 함수를 만들고, n의 제곱을 찾아 행렬에 n을 곱하는 함수를 만들었습니다. 여기서 (0)(0)-인덱스는 N+1번째 인덱스에 해당합니다.
4. 중간에 행렬 곱셈을 계산할 때 그 수를 필수 조건인 1000000007로 나누지 않으면 매우 큰 수이고 그에 대한 연산이 매우 커지므로 시간이 많이 걸린다. 그래서 중간에 한 번은 쪼개야 합니다.
5. 이렇게 구한 N번째 피보나치 수열을 이용하여 홀수 피보나치 수열의 합을 구하고자 합니다.
6. 피보나치 수열의 재귀 방정식(f(n+1)=f(n)+f(n-1))을 이용하여 홀수 피보나치 수열 합의 규칙성을 구한다.
에프(1) = 에프(2) – 에프(0)
에프(3) = 에프(4) – 에프(2)
에프(5) = 에프(6) – 에프(4)
….
f(2k+1) = f(2k)-f(2k-1)
이제 좌변과 우변의 합을 더하면
∑(2k+1) = f(2k) – f(0)의 형태를 얻을 수 있고, f(0) = 0이므로 ∑(2k+1) = f(2k)를 얻을 수 있다.
즉, n이 홀수인 경우
∑(n) = f(n+1)로 구해진다. 예) n = 5일 때, f(1)+f(3)+f(5) = f(6)
반대로 n이 짝수이면
∑(n) = f(n)으로 구할 수 있습니다. 예) n = 8일 때, f(1)+f(3)+f(5)+f(7) = f(8)
7. 이렇게 찾은 규칙으로 답을 출력하세요.

나는 그것을 느꼈다

분할 정복으로 피보나치 수열을 구하고 홀수 피보나치 수의 합을 찾는 데 사용하는 것은 문제입니다. 공식만 알면 쉽게 풀 수 있는 문제였습니다.