백준 2749번 피보나치 수 3

< 백준 2749번 피보나치 수 3 - 마포 코딩박 >

사용한 알고리즘: 수학 (피사노 주기)


 피보나치 수를 K 로 나눈 나머지는 일정한 주기를 갖습니다. 이를 피사노 주기라고 합니다.
문제에서는 피보나치 수를 1000000로 나눈 나머지를 구하라 하였으므로 이 또한 피사노 주기를 갖습니다.
 저는 이 피사노 주기를 구해 문제를 해결하였습니다.

문제풀이는 다음과 같습니다.
(1) (코드: 20~34)
 MOD = 1000000 라 할 때 주기를 찾습니다.
 처음 시작이 0번째 피보나치수 = 0, 1번째 피보나치수 = 1 이므로 

 k번째%MOD = 0 , k+1번째%MOD = 1 이 되면, 주기가 발생합니다.
 왜냐하면 이후 k+2번째%MOD = k번째%MOD + k+1번째%MOD = 0+1 = 1 , 

 k+3번째%MOD = k+1번째%MOD + k+2번째%MOD = 1 +1 = 2, ... 일 수 밖에 없기 때문입니다.

(2) (코드: 36~50)
 입력받은 N번째 피보나치수 = (N%주기)번째 피보나치수 입니다.
 이를 찾아 출력해 줍니다.

 피사노 주기라는 개념을 알면 어렵지 않게 해결할 수 있는 문제였습니다.