백준 11444 java - 피보나치 수 6

문제, 입출력, 테스트케이스

50분 타이머 기준 46분 1초만에 풀고 제출완료!

해당 문제는 그냥 우연찮게 맞추게 된 문제이다. 이리 저리 생각하다가 그냥 점화식을 행렬로 만들어볼까? 해서 그냥 만들어본 행렬의 곱이 피보나치수열이길래 행렬거듭제곱을 통해서 풀게 된 문제이다.

<문제 접근/풀이과정>
1. 1 =< n <= 1,000,000,000,000,000,000인 자연수이며, n번째 피보나치 수를 찾으시오.
-> long으로 변수 선언해야겠다
2. dp도 안되고 뭐도 안되고 이건 O(N)시간복잡도도 안되겠네?
-> O(logN) 시간복잡도를 만들어야하는구나
3. 분할정복이 맞다!
4. 근데 어떻게 하지? 이전 배운 분할 정복은 곱셈, 행렬거듭제곱인데?
5. 행렬로 해볼까?
6. 행렬로 어떻게 피보나치 수열 점화식을 짜지?
7. 이렇게 하면 되려나? -> 이게 되네?
8. 코딩하자!
참고 : 모듈러연산 (A 연산 B) mod p= (A mod p 연산 B mod p) (나눗셈 연산은 페르마 소정리를 이용한 역원을 통해 곱셈으로 연산을 바꾼 후 모듈러 연산 가능!

뭔가 우연으로 풀게되서 실력이 아닌 것 같지만 그래도 도출하고 코딩까지 했으니 이전보다 실력이 늘어난 건 맞겠지!

행렬거듭제곱은 https://chaaany.tistory.com/47?category=957446 이 게시글을 참고하면 좋다!

백준 10830 java - 행렬 제곱

<구현한 소스코드>

package boj;

import java.util.Scanner;

public class Boj_11444 {
	// f(n) = f(n-1) + f(n-2)
	// f(2) = f(1) + f(0) = 1
	// f(3) = f(2) + f(1) =
	// f(3) = (f(1) + f(0)) + f(0)
	// f(4) = (f(1) + f(0)) + f(0) + (f(1) + f(0))
	// f(5) = (1 + 1) + 1
	// f(6) = (1 + 1 + 1) + (1 + 1)
	// f(7) = (1 + 1 + 1 + 1 + 1) + (1 + 1 + 1)
	// f(n) = f(n-2) + f(n-3) + f(n-2)
	// f(n) = 2*f(n-2) + f(n-3)
	// 1 1 f(n-1) f(n-2) => 피보나치
	// 1 1 f(n-2) f(n-3)
	// f(3) = 1
	// f(4) = 1 + 1 = 1*1 + 1*1
	// f(5) = 1 + 1 + 1 = 2*1 + 1*1
	// f(6) = 1 + 1 + 1 + 1 + 1 = 3 + 2
	// f(7) = (1 + 1 + 1 + 1 + 1) + (1 + 1 + 1) = 5 + 3
	// f(n) = 2*f(n-2) + f(n-3)
	// A1 1 1 A2 2 1 A3 3 2 A4 5 3 ...
	//    1 0    1 1    2 1    3 2    
	static long arr[][] = { { 1L, 1L }, { 1L, 0L } };

	public static void main(String[] args) {

		Scanner sc = new Scanner(System.in);

		long n = sc.nextLong();
		if (n == 1) {
			System.out.println(1);
		} else {
			System.out.println(power(n - 1, 1000000007)[0][0]%1000000007);
		}
	}

	private static long[][] power(long y, long p) {
		long[][] answer = new long[2][2];
		for (int i = 0; i < 2; i++) {
			answer[i][i] = 1L;
		}
		while (y > 0) {
			if ((y & 1) == 1) {
				answer = matrixByMatrix(answer, arr, p);
			}
			arr = matrixByMatrix(arr, arr, p);
			y >>= 1;
		}
		return answer;
	}

	private static long[][] matrixByMatrix(long[][] answer, long[][] arr2, long p) {
		long[][] temp = new long[2][2];
		for (int i = 0; i < 2; i++) {
			for (int j = 0; j < 2; j++) {
				for (int k = 0; k < 2; k++) {
					temp[i][k] += (answer[i][j] * arr2[j][k]) % p;
				}
			}
		}
		return temp;
	}
}