피보나치 수 문제 (피사노 주기,행렬의 곱셈)

피보나치 수를 구하는 3가지 방법.

피보나치 수는 알다시피 다음과 같이 정의되는 수열이다.

 

이렇게 이전 2개의 합이 다음 오는 수가 되는 수열이다.

조금 나열하면 0, 1, 1, 2, 3, 5, 8, 13, 21, 34, 55, 89, 144, ...이 된다.

 

 

가장 기본적인 문제를 풀어보자

 

10826 피보나치 수 4  www.acmicpc.net/problem/10826

1.접근

n은 10,000보다 작거나 같은 자연수 또는 0이다. 쉬운 피보나치 수이다.

2.풀이

우리는 DP느낌의 방법으로 쉽게 O(N)시간에 답을 구할 수 있다.

3.코드

4.배운점

• 사실 dp로 구현했었는데 메모제이션 할 필요없이 for 문을 돌리면 가장 간단했다.

 

2749 피보나치 수 3  www.acmicpc.net/problem/2749

1.접근

n은 1,000,000,000,000,000,000보다 작거나 같은 자연수이다. 기본적인 방법으로는 풀 수 없다.

하지만 이 문제는  n번째 피보나치 수를 1,000,000으로 나눈 나머지를 출력한다고 써 있다.

이 문제를 풀려면 피사노 주기에 대해 알 필요가 있다.

피사노 주기

피보나치 수열을 임의의 수 m으로 나눈 나머지는 주기를 이룬다.

11로 나눈 피보나치 수열을 보자.

 

 

 

 

위 그림에 따라서 피사노 주기는 10이 된다. 피사노 주기는 다음의 성질을 가진다.

• m > 2인 경우에 k(m)은 짝수이다.
• 임의의 짝수 정수 n > 2에 대해서, k(m) = n인 m이 항상 존재한다.
• k(m) ≤ m^2 - 1
• k(2n) = 3×2(n-1)
• k(5n) = 4×5n
• k(2×5n) = 12x5n
• n > 2라면, k(10n) = 15×10(n-1)

백준 피사노주기 문제를 풀고 오는것도 좋다.www.acmicpc.net/problem/9471

2.풀이

바로위에 정리에 따르면 우리가 나누는 나머지 1,000,000는 피사노 주기를 적용하기 좋은 수다.

k(10n) = 15×10(n-1).  따라서 우리는 주기만큼의 피사노 수열을 구한다.

그후 n을 피사노 수열의 길이로 나눈 나머지를 구한후 그 나머지를 피사노 수열의 인덱스로 쓰면 된다.

 

다음과 같은 큰 특징이 안보일 때는 dp를 하면서 초기 시작값인 1,1이 돌아오는 지점을 찾으면 된다.

3.코드

4.배운점

• 0,1로 돌아오는 지점을 찾았었는데 1,1을 찾아야 했다.
• 모듈러가 너무크면 못 쓸것이다

 

11444 피보나치 수 6 www.acmicpc.net/problem/11444

1.접근

n은 1,000,000,000,000,000,000보다 작거나 같은 자연수이다.

n번째 피보나치 수를 1,000,000,007으로 나눈 나머지를 출력한다.

n도 너무 크고 나누는 수도 너무크다. 이럴 땐 행렬의 거듭제곱을 활용한다.

 

피보나치 수를 행렬로 표현하면 다음과 같다.

 

 

 

이에 공식에 따라서 우리는 n번째 피보나치 수를 구하려면

 

행렬 [[1,1],[1,0]]의 n-2승을  초기 값 F1=1과 F2=1값에 곱한 값이 Fn,Fn-1이 나온다는걸 유도할 수 있다.

 

2.풀이

n이 어마어마하게 크지만 우리는 제곱수를 O(logn)의 시간에 구할 수 있다.

(분할정복 1629 곱셈 www.acmicpc.net/problem/1629)

 

따라서 [[1,1],[1,0]]의 n-2승 값을 먼저 구해준 후 초기값 1,1과 행렬의 곱셈을 해준다면 쉽게 구할 수 있다.

행렬의 곱셈을 할 때 모듈러 연산은 곱셈,덧셈,뺄셈에 대해서 분배법칙이 성립하므로 덧셈한걸 나눈 값으로 넣어준다.

 

3.코드

4.배운점

• 피보나치를 행렬로 표현할 수 있다고 생각 못했다
• n이 너무 크거나 나누는 m이 너무 크다면(생각이상으로) 새로운 방법을 항상 찾아야한다.