읽기 전
- 불필요한 코드나 잘못 작성된 내용에 대한 지적은 언제나 환영합니다.
- 개인적으로 배운 점을 정리한 글입니다.
문제 링크
문제 풀이
주어진 입력이 너무나도 크다. O(n)O(n)으로 구해도 답이 없는 수준이다. 따라서 기존 DP 기반으로 피보나치 수를 구하면 여지없이 시간초과가 날 것이다. 따라서 제곱의 형태로 곱해나가 정답을 도출하는 O(log n)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 |