오늘은 피보나치 수열을 접근하는 새로운 방법을 배웠다.
일단 이 문제는 풀기에 실패했다.(고민시간 30분 초과)
지금의 과정은 이런 접근방법이 있다는 것을 확장하는 단계이기 때문에
좌절하지 말고 꾸준히 문제를 풀어보자
오늘도 🏃♀️🏃♂️🏃🏃♂️
접근
"피보나치 수열"은 동적계획법 또는 재귀함수로 풀 수 있는 어쩌면 엄청 쉬운 문제이다. 하지만 여러가지 조건이 붙었을 때 단순히 저 방법만을 생각해서는 풀 수 없는 문제가 있는거 같다. 오늘 푼 이 문제도 그러하다.
조건을 살펴보자
입력으로 주어지는 값의 범위가 최대 1,000,000,000,000,000,000이다.
long으로 받자.
오버플로우가 발생하기 때문에 출력값에 대해서
n번째 피보나치 수를 1,000,000,007으로 나눈 나머지를 출력한다.
-
처음에 동적계획법을 활용해서 dp[]을 선언하자라고 생각했다.
그러나 위와 같은 문제가 발생했다.
일단 index로 들어가야 하는 배열의 범위는 int 정수형만 가능하다.
나와 같은 질문을 stack overflow에 질문한 사람이 있었고 그에 대한 답변은 위와 같다.
번역 결과
어떤 이유에서인지 인덱스가 길게 저장되어 있는 경우 int에 캐스트한 다음 배열을 인덱싱하십시오. Java에서 Integer로 인덱싱할 수 없을 정도로 충분히 큰 배열을 만들 수 없습니다. 따라서 여기에는 긴 정수가 필요하지 않습니다
-
따라서 이 문제는 동적계획법으로 풀지 못한다. 배열에 저장할 수 없기 때문이다. 그렇다면 어떻게 접근해야할까?
바로 행렬을 통해서 접근하는 것이다.이걸 떠올릴 수 있어야 했는데 그렇지 못했고 다른 분들의 풀이를 참고해서 정리해보려고 한다.
과정
이분의 풀이를 참고해서 정리합니다.
1.
위와 같이 처음에 접근할 수 있다. 그러나 이를 b=Ax 형태로 나타내야 하기 때문에
2.
위와 같은 형식을 만든다.
3. 
결론적으로 위와 같이 표현할 수 있고
5. 
A의 n승만으로도 구하고자 하는 Fn을 구할 수 있다.
A의 n승을 구할 때
A의 n/2를 통해서 반절의 연산을 통해서 구하도록 풀이를 구현하도록 하자.
풀이(java)
import java.util.*;
import java.io.*;
public class Main{
static long[][] origin = {{1,1},{1,0}};
static long remain = 1000000007;
public static void main(String[] args) throws IOException{
BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));
long N = Long.parseLong(br.readLine()); // 자연수, long
long[][] A = {{1,1},{1,0}};
long answer = pibo(A,N-1)[0][0];
bw.write(answer+"");
bw.flush();
bw.close();
br.close();
}
static long[][] pibo(long[][] A, long N){
if(N==0 || N==1){
return A;
}else{
long[][] sub_A = pibo(A,N/2);
sub_A = mutiple(sub_A,sub_A);
if(N%2==1L){
sub_A= mutiple(sub_A,origin);
}
return sub_A;
}
}
static long[][] mutiple(long[][] a, long[][] b){
long[][] ab = new long[2][2];
ab[0][0]= (a[0][0]*b[0][0]+a[0][1]*b[1][0])%remain;
ab[0][1]= (a[0][0]*b[0][1]+a[0][1]*b[1][1])%remain;
ab[1][0]= (a[1][0]*b[0][0]+a[1][1]*b[1][0])%remain;
ab[1][1]= (a[1][0]*b[0][1]+a[1][1]*b[1][1])%remain;
return ab;
}
}