[BOJ] 11444. 피보나치 수 6 - JAVA

🔗 문제

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

11444번: 피보나치 수 6

 

💻 풀이 및 코드

문제 유형 : 분할정복을 이용한 거듭제곱

 

Fn = Fn-1 + Fn-2 인 피보나치 수 중 N 번째 값을 구하는 문제

 

풀이

자세한 설명은 아래로!

https://st-lab.tistory.com/252

[백준] 11444번 : 피보나치 수 6 - JAVA [자바]

---

일단 피보나치 수는 DP 로 풀 수 있다. 하지만 N 의 범위가 최대 1,000,000,000,000,000,000 이기 때문에 DP 로 푼다면 O(N) 라고 할 때, 10억 당 1초가 걸린다고 연산을 한다면 제한시간인 1초를 훌쩍 넘는다. 대략 걸리는 시간을 반으로 줄여야겠다라고 생각을 했다. 여기서 분할정복의 거듭제곱 개념을 활용해서 시간을 반으로 줄일 수 있다.

 

나는 간략하게 결론만 정리할 것이기 떄문에 자세한 설명은 위에 적어놓은 사이트를 들어가면 자세히 잘 설명해놨다.

 

• 먼저 위와 같은 피보나치 공식을 행렬 꼴로 만든다.
• 왜 행렬 꼴로 만드나면, 선형 방정식을 풀 때 여러 개의 연립방정식이 주어진다면 식을 뺴고 더하면서 미지수를 풀어내는 방식으로 많이 풀이했을 것이다. 하지만, 수식이 복잡해지고 많아지면 방정식끼리 더하고 빼고 하는 과정도 복잡해질뿐더러 시간도 오래 걸린다. 하지만, 여러 개의 방정식을 하나의 행렬 꼴로 표현하게 될 경우 선형방정식의 해가 존재하는지 없는지 판단을 하기 쉬워질 뿐 더러 가우스 소거, 크래머 공식 등 여러 방법에 의해 쉽게 미지수에 대한 답 혹은 일반항을 찾을 수 있다. 
  즉, 우리가 해야 할 일은 선형방정식을 행렬 꼴(matrix form) 로 변화하는 것이다. 좀 더 쉽게 말하자면 위 방정식을 Ax = b 형태의 행렬로 만드는 것이다.

• 다음과 같이 만들 수 있다.
• 이것만으로는 행렬 연산을 통해 의미를 얻을 수 있는 수식이 아니기 때문에 간단한 식을 하나 더 추가한다.

 

이제 ⓐ 와 ⓑ 를 결합해보자.

• 일반화를 위해 Fn+1 과 Fn 을 하나의 열벡터로 보고 Un 으로 변경을 해보자.

이제 u 벡터에 대해 한 번 풀어보자.

일단, 우리는 u0 에 대한 초기값을 알 수 있다.

 

u1 부터 나열을 해 보면

• 결과적으로 우리는 un = A^n u0 라는 A 라는 행렬의 n 제곱으로 구할 수 있다는 것이다.

 

 

느낀 점

• 공학에서 선형대수는 필수적인 존재고, 선형대수가 AI(인공지능), 그래픽스 등과 관련이 있다고 해서 풀어봤다.

 

전체 코드

import java.io.*;
import java.util.*;

public class Main_bj_11444_피보나치수6 {

	static int P = 1_000_000_007;
	
	public static void main(String[] args) throws Exception {
		System.setIn(new FileInputStream("res/input_bj_11444.txt"));
		Scanner sc = new Scanner(System.in);
		long N = sc.nextLong();		// N 이 1이라면
		
		long[][] A = {{1, 1}, {1, 0}};
		
		//Fn 은 A^n-1 의 [0][0] 을 출력한다.
		System.out.println(pow(A, N-1)[0][0] % P);
		sc.close();
		
	}
	
	static long[][] pow(long[][] base, long expo) {
		if(expo == 1 || expo == 0) {
			return base;
		}
		
		long[][] res = new long[2][2];
		res = pow(base, expo/2);
		res = multiply(res, res);
		
		
		if(expo % 2 == 0) {
			return res;
		} else {
			return multiply(res, base);
		}
		
	}
	
	static long[][] multiply(long[][] a, long[][] b) {
		long[][] res = new long[2][2];
		
		res[0][0] = ((a[0][0] * b[0][0]) + (a[0][1] * b[1][0])) % P;
		res[0][1] = ((a[0][0] * b[0][1]) + (a[0][1] * b[1][1])) % P;
		res[1][0] = ((a[1][0] * b[0][0]) + (a[1][1] * b[1][0])) % P;
		res[1][1] = ((a[1][0] * b[0][1]) + (a[1][1] * b[1][1])) % P;
		
		return res;
	}

}

 

---

Reference

https://st-lab.tistory.com/252

[백준] 11444번 : 피보나치 수 6 - JAVA [자바]