[백준온라인] 11444번 피보나치 수 6

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

11444번: 피보나치 수 6

문제 요약 : n 번째 피보나치수를 1000000007로 나눈 나머지 출력

입력	출력
1 ≤ n ≤ 1000000000000000000 (10^18)	n 번째 피보나치수를 1000000007로 나눈 나머지 출력

JAVA

소스코드 : https://github.com/cbkpar/BOJ/blob/main/boj_11444.java

채점 번호	아이디	문제 번호	결과	메모리	시간	언어	코드 길이
31653078	cbkpar	11444	맞았습니다!!	14312KB	140ms	Java 11	978B

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;

public class Main {
	
	public static void main(String args[]) throws IOException {
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		int i,j,k;
		long n;
		long[][] narr = new long[2][2];
		long[][] tarr = new long[2][2];
		n = Long.parseLong(br.readLine());
		n--;
		narr[0][0] = narr[1][1] = 1;
		tarr[0][0] = tarr[0][1] = tarr[1][0] = 1;
		while(n>0) {
			if(n%2==1) {
				long[][] sarr = new long[2][2];
				for(i=0;i<2;i++) for(j=0;j<2;j++) for(k=0;k<2;k++) sarr[i][j] += narr[i][k]*tarr[k][j];
				for(i=0;i<2;i++) for(j=0;j<2;j++) narr[i][j] = sarr[i][j]%1000000007;
			}
			long[][] sarr = new long[2][2];
			for(i=0;i<2;i++) for(j=0;j<2;j++) for(k=0;k<2;k++) sarr[i][j] += tarr[i][k]*tarr[k][j];
			for(i=0;i<2;i++) for(j=0;j<2;j++) tarr[i][j] = sarr[i][j]%1000000007;
			n/=2;
		}
		System.out.println((narr[1][0]+narr[1][1])%1000000007);
		
	}
}

이 문제를 풀기 위해서는 위와 같은 식을 이용해 구해야 한다.

이때 n이 상당히 크므로 한번씩 계산하면 시간 초과가 난다.

 

초기에는 narr을 단위행렬(E), tarr을 {{1,1},{0,1}}로 초기화하고

sarr을 배열의 복사를 위해 사용한다.

 

이때 F_n+1값을 구하게 되므로 n에서 1을 빼고 다음과 같이 진행한다.

n이 0보다 클때까지

1. n을 2로 나눴을 때 나머지가 1 일 경우에는 narr에 tarr을 곱해주고 tarr을 거듭제곱해준다.

2. n을 2로 나눴을 때 나머지가 0 일 경우에는 tarr을 거듭제곱해준다.

3. n을 2로 나눠준다.

 

n이 0이 됐을 경우 (c+d) 값을 1000000007로 나눈 나머지를 출력하면 된다.

 

예제 ) n = 1000일 경우

n에서 1을 빼주고 위 과정을 진행한다.