divide and conquer 3

문제는 더블릿 10 divide and conquer에 있는 mod_fibo입니다.

문제 사이트 주소입니다.

http://183.106.113.109/30stair/mod_fibo/mod_fibo.php?pname=mod_fibo

엄청 큰 피보나치 수를 구하는게 문제입니다.

피보나치 수열의 단순한 방법(전전값과 전값의 합)으로는 시간초과가 뜹니다.  나눗셈을 미리 해주는 방법도 마찬가지로 시간초과가 납니다.

풀기 위해서는 행렬을 이용해주는 방법이 있습니다.

1 1

1 0

을 피보나치 수열의 0, 1, 1, 2, 3, 5, 8, 13, 21, 34, 55...에서 첫번째 1에 해당하는 행렬로보고 값은 0행 0열의 값을 봅니다.

이 행렬을 제곱하면 

2 1

1 1

이 나오고 이 값은 2에 대항하는 행렬입니다.

이 행렬을 제곱하면

5 3

3 2  =  5에 해당

제곱하면

34 21

21 13 = 34에 해당

...

이렇게 행렬의 곱을 통해 피보나치의 다음 값을 구합니다.

제곱에 해당하는 위치의 값이 아닌 다음 값을 구하려면

1 1

1 0 

을 곱해주면 됩니다.

그럼 11번째에 해당하는 값을 구하고자 한다면

10행렬                                                      * 1행렬

5행렬                                         * 5행렬

4행렬                            * 1행렬       

2행렬             * 2행렬

1행렬*1행렬

과 같이 재귀를 통해 밑에서부터 구해서 올라가면 됩니다.