Processing math: 100%

읽기 전

  • 불필요한 코드나 잘못 작성된 내용에 대한 지적은 언제나 환영합니다.
  • 개인적으로 배운 점을 정리한 글입니다.

문제 링크

BOJ #11444 피보나치 수 6

문제 풀이

주어진 입력이 너무나도 크다. O(n)으로 구해도 답이 없는 수준이다. 따라서 기존 DP 기반으로 피보나치 수를 구하면 여지없이 시간초과가 날 것이다. 따라서 제곱의 형태로 곱해나가 정답을 도출하는 O(log n)해법을 생각해내야 한다.

이 문제는 초기값을 (f2f1\f1f0)으로 설정해두고 그에 대한 제곱값이 피보나치 수의 형태로 만들어진다는 사실을 모르면 해결하기가 쉽지 않다. (f2f1\f1f0)=(11\10)이고 (11\10)2=(21\11)=(f3f2\f2f1)임을 알 수 있어 이 점을 이용해야 한다.

python 코드

import sys
input = sys.stdin.readline
def mutiply(arr1, arr2):
R, C, M = len(arr), len(arr2[0]), len(arr1[0])
sol = [[0 for _ in range(C)] for _ in range(R)]
for i in range(R):
for j in range(C):
b = 0
for k in range(M):
b += arr1[i][k] * arr2[k][j]
sol[i][j] = b % 1000000007
return sol
def solve(n):
if n == 1:
return matrix
t = solve(n // 2)
t = multiply(t, t)
if n % 2 == 1:
t = multiply(t, matrix)
return t
N = int(input())
matrix = [[1, 1], [1, 0]]
if N > 1: # N이 1보다 크면
result = solve(N - 1) # [0][0]은 f_2부터 시작이므로 N - 1을 입력
print(result[0][0])
else: # N이 1이면
print(matrix[0][0])

'Algorithms > Baekjoon' 카테고리의 다른 글

BOJ #9251 LCS  (0) 2021.07.28
BOJ #11054 가장 긴 바이토닉 부분 수열  (0) 2021.07.28
BOJ #12865 평범한 배낭  (0) 2021.07.28
BOJ #11053 가장 긴 증가하는 부분 수열  (0) 2021.07.26
BOJ #10844 쉬운 계단 수  (0) 2021.07.26

+ Recent posts