728x90
🔗 문제 링크
https://www.acmicpc.net/problem/11444
📌 문제 개요
N번째 피보나치 수를 구하는 문제
하지만 N의 크기가 매우 크기 때문에 일반적인 DP(O(N)) 방식으로는 시간 초과가 발생합니다.
📌 접근 방법
이 문제는 피보나치를 행렬 형태로 변환하여 해결
기본 행렬:
|1 1|
|1 0|
이 행렬을 N번 곱하면 다음과 같은 결과가 나옵니다.
|F(n+1) F(n) |
|F(n) F(n-1)|
result[0][1] = F(N) 이 됩니다.
📌 핵심 아이디어
1. 행렬 거듭제곱
A^N을 빠르게 구하기 위해 분할 정복 사용
짝수: A^N = A^(N/2) × A^(N/2)
홀수: A^N = A^(N/2) × A^(N/2) × A
2. 행렬 곱셈
“가로 × 세로” 방식으로 계산
result[0][0] = a00*b00 + a01*b10
result[0][1] = a00*b01 + a01*b11
result[1][0] = a10*b00 + a11*b10
result[1][1] = a10*b01 + a11*b11
📌 처리 흐름
입력 N
→ 기본 행렬 생성
→ pow(base, N)
→ result[0][1] 출력
📌 전체 코드
import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
public class Main {
static final long MOD = 1000000007L;
public static void main(String[] args) throws IOException {
BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
long N = Long.parseLong(br.readLine());
// 피보나치 상자
long[][] base = {
{1, 1},
{1, 0}
};
// 피보나치 상자를 N번 사용한 결과
long[][] result = pow(base, N);
// 그 결과에서 F(N)이 들어있는 칸을 출력
System.out.println(result[0][1]);
}
// 상자를 빠르게 여러 번 사용하는 방법
static long[][] pow(long[][] matrix, long exp) {
// 1번이면 그냥 자기 자신
if (exp == 1) {
return matrix;
}
// 빠른 방식 (분할 정복) - A^8 = (A^4) × (A^4)
long[][] half = pow(matrix, exp / 2);
long[][] result = multiply(half, half);
// 홀수 처리 - A^5 = A^2 × A^2 × A
if(exp % 2 == 1){
result = multiply(result, matrix);
}
return result;
}
// 상자 2개를 합쳐서 더 큰 상자 만드는 것
static long[][] multiply(long[][] a, long[][] b){
long[][] result = new long[2][2];
// 규칙 : 가로줄 × 세로줄 해서 더한다
// [1 1] [1 1] [2 1]
// [1 0] x [1 0] = [1 1]
result[0][0] = (a[0][0] * b[0][0] + a[0][1] * b[1][0]) % MOD;
result[0][1] = (a[0][0] * b[0][1] + a[0][1] * b[1][1]) % MOD;
result[1][0] = (a[1][0] * b[0][0] + a[1][1] * b[1][0]) % MOD;
result[1][1] = (a[1][0] * b[0][1] + a[1][1] * b[1][1]) % MOD;
return result;
}
}
📄 정리
이 문제는 단순 피보나치가 아니라
행렬 거듭제곱 + 분할 정복 을 사용하는 문제입니다.
- 피보나치를 행렬로 표현
- 분할 정복으로 빠르게 계산
- 결과에서 F(N) 위치 추출
- 피보나치를 행렬로 바꿔서 O(log N)으로 계산하는 문제
728x90
'코테(Solved.ac + Programmers)' 카테고리의 다른 글
| 백준 [2851] 슈퍼 마리오 JAVA 풀이 (브루트포스, 누적합) (0) | 2026.04.25 |
|---|---|
| 백준 4008 특공대 JAVA 풀이 (DP, CHT, 누적합, 시간복잡도) (0) | 2026.04.24 |
| 백준 1149 RGB 거리 JAVA 풀이 (DP, 누적 최소값, 시간복잡도) (0) | 2026.04.24 |
| [백준] 트리 순회 JAVA 풀이 (트리, 재귀, DFS) (0) | 2026.04.21 |
| 백준 13548 수열과 쿼리 6 JAVA 풀이 (Mo's Algorithm, 오프라인 쿼리) (0) | 2026.04.20 |