문제 출처: https://www.acmicpc.net/problem/11444
1. 결과
메모리 29200KB, 시간 88ms
2. 풀이
이 문제는 평범한 재귀 호출이나 동적 계획법과 같은 연산을 통해 구하기가 쉽지 않다. 문제 조건에서 볼 수 있듯이 Fn을 구하는데, 해당 n이 최대 10^17(10의 17제곱)까지 가능하기 때문이다. 또한 피보나치 수열은 궁극적으로 앞의 연속된 두 숫자를 알아야만 그 다음 숫자를 구할 수 있고, 앞의 연속된 두 숫자는 또 해당 숫자의 앞의 연속된 두 숫자를 알아야만 연산이 가능하다. 즉, 기존의 피보나치 수열 개념( Fn = Fn-1 + Fn-2 (n ≥ 2) )은 연쇄적으로 연산이 되기 때문에, 각각의 독립된 소문제 해결을 통해 큰 문제를 해결하는 일반적인 분할 정복 방식도 적용하기가 쉽지 않다.
해결 방법을 고민하던 중, 피보나치 수열을 초기값(F0 = 0, F1 = 1)과 행렬( [[1, 1], [1, 0]] )의 곱 또는 2 이상의 제곱을 통해 해결할 수 있다는 것을 알 수 있었다. 그리고 더 나아가 [[Fn+1, Fn], [Fn, Fn-1]]은 [[1, 1], [1, 0]]의 곱 또는 제곱만으로 연산이 가능했다. 이는 재귀 호출로만 가능한 줄 알았던 문제를 분할 정복법을 이용한 행렬의 제곱 연산 문제로 변환할 수 있는 포인트였다.
분할 정복법을 이용한 행렬의 큰 수 제곱 연산은 이전에도 구해본 적이 있었기 때문에 어렵지 않게 구현할 수 있었으며, 1,000,000,007로 나눈 나머지를 결과로 가져와야 한다는 점까지 잊지 않고 연산에 포함했다. 여기서도 곱셈에서의 나머지 연산 규칙( (A*B) % P = ((A%P) * (B%P)) % P )이 적용될 수 있기 때문에, 각각의 행렬 연산에도 나머지 연산을 적용시키며 어떤 과정에서든 숫자가 너무 커지지 않도록 방지했다.
그리고 피보나치 수를 구하는 문제가 이 문제의 제목만 봐도 최소 6가지의 경우가 존재한다는 것을 알 수 있다. 나중에는 한 번 이런 시리즈 문제 풀이 방법을 모아서 정리해보는 것도 재밌을 것 같다.
import sys
# 행렬의 곱으로 피보나치 수열 연산 가능
# [[Fn+1, Fn], [Fn, Fn-1]] = [[1, 1], [1, 0]] ^ n
def dotAB(a, b):
result = [[0] * 2 for _ in range(2)]
for i in range(2):
for j in range(2):
for k in range(2):
result[i][j] += a[i][k] * b[k][j]
result[i][j] %= 1000000007
return result
def getFibonacci(arr, n):
if n == 1: return arr
fibo = getFibonacci(arr, n//2)
if n % 2: return dotAB(arr, dotAB(fibo, fibo))
else: return dotAB(fibo, fibo)
def main():
n = int(sys.stdin.readline())
fibo_arr = [[1, 1], [1, 0]]
Fn = getFibonacci(fibo_arr, n)[0][1]
return Fn % 1000000007
if __name__ == "__main__":
print(main())
'지극히 개인적인 공부 노트 > 알고리즘(Algorithm)' 카테고리의 다른 글
[Algorithm] 백준 1260번: DFS와 BFS | 기본적인 DFS, BFS 구현 (0) | 2021.09.07 |
---|---|
[Algorithm] 백준 10942번: 팰린드롬? | 동적 계획법 응용 (0) | 2021.09.06 |
[Algorithm] 백준 11401번: 이항 계수 3 | 페르마의 소정리, 약수의 나머지 곱을 통한 나머지 연산 (0) | 2021.09.01 |
[Algorithm] 백준 1780번: 종이의 개수 | 분할 정복, 전역 변수 (0) | 2021.09.01 |
[Algorithm] 백준 10773번: 제로 | 클래스로 스택 구현 (0) | 2021.09.01 |