[백준] 11444번 : 피보나치 수 6 - 파이썬(Python) - 우당탕탕 개발자 되기 프로젝트

 

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

 

1. 문제 설명

반응형

2. 풀이과정

해당 문제는 선형대수 지식이 요구되는 문제이다.

피보나치 수를 행렬로 나타내면 아래와 같은 식으로 나타낼 수 있다.

해당 행렬을 활용하여 피보나치 수를 10830번 : 행렬 제곱 문제와 동일하게 분할 정복 알고리즘으로 해결한다.

피보나치 수를 행렬로 나타내는 선형대수 지식만 알고 있었다면 쉽게 해결할 수 있는 문제지만, 해당 선형대수 지식이 쉽게 떠오르지 않는다.

해당 문제를 해결하면서 선형대수 지식을 다시 한번 상기시켜 봤다.

 

1. sys.stdin.readline() 함수를 사용하기 위해 sys 모듈을 불러온다. import sys
2. 구하고자 하는 피보나치 수의 번호를 입력받는다. N = int(sys.stdin.readline())
3. 구한 피보나치 수를 1,000,000,007으로 나눈 나머지를 구해야 하므로 해당 수를 변수로 저장해 둔다. p = 1000000007
4. 두 행렬을 곱하는 함수를 생성한다. def matrix_mul(m1, m2)
   1. 결과는 2x2 행렬로 구해지므로 결과를 저장할 행렬을 생성한다. result = [[0, 0], [0, 0]]
   2. 각 위치별로 결과 행렬의 값을 구한 뒤, 1,000,000,007으로 나눈 나머지를 저장한다.
   3. result[0][0] = (m1[0][0] * m2[0][0] + m1[0][1] * m2[1][0]) % p
   4. result[0][1] = (m1[0][0] * m2[0][1] + m1[0][1] * m2[1][1]) % p
   5. result[1][0] = (m1[1][0] * m2[0][0] + m1[1][1] * m2[1][0]) % p
   6. result[1][1] = (m1[1][0] * m2[0][1] + m1[1][1] * m2[1][1]) % p
   7. 구한 최종 결과 행렬을 반환한다. return result
5. 거듭제곱 연산을 분할 정복 알고리즘으로 해결하는 함수를 생성한다. def divide(b)
   1. 만약 거듭제곱의 지수가 1이면 기본 행렬을 반환한다. if (b == 1): return matrix
   2. 반면 거듭제곱의 지수가 2 이상이면 else
      1. 지수를 2로 나눈 몫의 결과로 함수를 다시 수행하여 결과를 저장한다. res = divide(b // 2)
      2. 만약 지수가 짝수이면 구한 결과 행렬을 두 번 곱한다. if (b % 2 == 0): return matrix_mul(res, res)
      3. 반면에 지수가 홀수이면 구한 결과 행렬을 두 번 곱하고 기본 행렬을 한 번 더 곱해준다. else: return matrix_mul(matrix_mul(res, res), matrix)
6. 기본 행렬은 위 피보나치 수를 행렬로 나타내었을 때의 행렬을 나타낸다. matrix = [[1, 1], [1, 0]]
7. 구할 피보나치 수를 분할 정복 알고리즘 함수에 넣어 반환된 결과 행렬을 정답에 저장한다. answer = divide(N)
8. 정답 행렬에서 구하려는 위치의 값을 추출해 1,000,000,007으로 나눈 나머지를 반환한다. print(answer[0][1] % p)

3. 소스코드

import sys

N = int(sys.stdin.readline())
p = 1000000007

def matrix_mul(m1, m2):
    result = [[0, 0], [0, 0]]

    result[0][0] = (m1[0][0] * m2[0][0] + m1[0][1] * m2[1][0]) % p
    result[0][1] = (m1[0][0] * m2[0][1] + m1[0][1] * m2[1][1]) % p
    result[1][0] = (m1[1][0] * m2[0][0] + m1[1][1] * m2[1][0]) % p
    result[1][1] = (m1[1][0] * m2[0][1] + m1[1][1] * m2[1][1]) % p

    return result

def divide(b):
    if (b == 1):
        return matrix
    else:
        res = divide(b // 2)
        if (b % 2 == 0):
            return matrix_mul(res, res)
        else:
            return matrix_mul(matrix_mul(res, res), matrix)
    
matrix = [[1, 1], [1, 0]]
answer = divide(N)
print(answer[0][1] % p)