[백준 11440] 피보나치 수의 제곱의 합 (python)

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

11440번: 피보나치 수의 제곱의 합

피보나치 수의 제곱의 합 문제

피보나치 수를 분할 정복을 이용해서 구하고, 규칙을 찾아서 구해주면 해결할 수 있는 문제

분할 정복만 잘하면 어렵지 않게 해결 가능!

반응형

⚙️ 내가 푼 정답 코드

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이 될 때까지 재귀 반복 
        # results += matrix[1][0]**2
        if n % 2 == 0: # 짝수면
            return mult(matrix, matrix) # 행렬끼리 곱해주기
        else: # 홀수면
            return mult(mult(matrix,matrix), x) # 행렬 곱한거에 한번 더 곱해주기
result = f(x,N)
print(result[0][1]*result[0][0] % 1000000007) # 피보나치 제곱들의 합 = 피보나치n+1 * 피보나치n 이므로

📌문제 접근 포인트

1. 먼저 피보나치 수열을 구해보자. N의 크키가 1조가 넘을정도로 매우 큰 숫자이기에 재귀 or DP로는 절대로 시간안에 들어오기 어려운 구조다.
2. 그렇다면 분할 정복을 이용해서 필요한 경우만 빠르게 찾아 낼 수 있도록 구성해보자. 피보나치 수열의 경우 행렬로 나타내면 [[1,1],[1,0]]의 형태의 반복된 곱으로 구할 수 있는 구조로 되어 있다. 이 행렬의 n제곱을 활용한 분할정복을 해보자.
3. 2개의 행렬을 곱해주는 행렬의 곱 함수를 만들어주고, n제곱을 구해줄 함수를 만들어 행렬을 n제곱 해주었고, 이때의 행렬의 [1][0] 인덱스에 해당하는 것으로 N번째 피보나치 수열을 구해줄 수 있다. 여기서 [0][0] 인덱스는 N+1번째 인덱스에 해당한다.
4. 그렇다면 제곱의 합은 어떻게 구할 수 있을지 규칙을 찾아보자
기본 피보나치 공식은 An+1 = An-1 + An 이고, 이걸 변형해주면 An = An+1 - An-1이다.
여기서 우리가 필요한건 An의 제곱이므로 각각의 좌우에 An을 곱해보자.
An*An = An(An+1-An-1) 을 구할 수 있다. 그럼 A0 = 0, A1 = 1이니 이것을 기반으로 구해보자.
A1*A1 = A1*A2 - A0*A1
A2*A2 = A2*A3 - A1*A2
A3*A3 = A3*A4 - A2*A3
....
An*An = An*An+1 - An-1*An
이므로 좌변, 우변끼리 다 더해주면 A1A1+A2A2+...+AnAn = An*An+1 - A0*A1을 얻을 수 있고, 결국 A0 = 0이니
제곱의 합 = An+1 * An 으로 표현할 수 있다.
5. 행렬에서 [0][0] 인덱스와 [1][0] 인덱스가 각각 An+1과 An에 해당하므로 둘의 곱을 결과로 출력하면 원하는 답을 얻을 수 있다.