[백준 11442] 홀수번째 피보나치 수의 합 (python)

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

11442번: 홀수번째 피보나치 수의 합

홀수번째 피보나치 수의 합 문제

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

분할 정복으로 피보나치 수들의 합을 구하고 홀수번쨰 피보나치 수의 규칙을 찾아보자.

⚙️내가 푼 정답코드

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조가 넘을정도로 매우 큰 숫자이기에 재귀 or DP로는 절대로 시간안에 들어오기 어려운 구조다.
2. 그렇다면 분할 정복을 이용해서 필요한 경우만 빠르게 찾아 낼 수 있도록 구성해보자. 피보나치 수열의 경우 행렬로 나타내면 [[1,1],[1,0]]의 형태의 반복된 곱으로 구할 수 있는 구조로 되어 있다. 이 행렬의 n제곱을 활용한 분할정복을 해보자.
3. 2개의 행렬을 곱해주는 행렬의 곱 함수를 만들어주고, n제곱을 구해줄 함수를 만들어 행렬을 n제곱 해주었고, 이때의 행렬의 [1][0] 인덱스에 해당하는 것으로 N번째 피보나치 수열을 구해줄 수 있다. 여기서 [0][0] 인덱스는 N+1번째 인덱스에 해당한다.
4. 중간에 행렬의 곱을 구할 때 요구 조건인 1000000007로 숫자를 나눠주지 않으면 굉장히 큰 숫자기에 이에 대한 연산이 굉장이 커져버리기에 시간이 많이 소비된다. 그렇기에 중간에 한번 나눠줄 필요가 있다.
5. 이렇게 구한 N번째 피보나치 수열을 활용해서 홀수 피보나치 수열들의 합을 구해보자.
6. 피보나치 수열의 점화식(f(n+1)=f(n)+f(n-1))을 이용해서 홀수 피보나치 수열의 합의 규칙성을 찾아보자.
f(1) = f(2) - f(0)
f(3) = f(4) - f(2)
f(5) = f(6) - f(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)로 얻어 진다. ex) n = 5일 경우 f(1)+f(3)+f(5) = f(6)
반대로 n이 짝수일 때는
∑(n) = f(n)으로 얻을 수 있다. ex) n = 8일 경우 f(1)+f(3)+f(5)+f(7) = f(8) 
7. 이렇게 찾은 규칙을 이용해서 답을 출력해보자.