백준 10826번 피보나치 수 4

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

사용한 알고리즘: big int 구현..?


 사실 big int 구현을 제공해주는 파이썬으로 풀면 쉬울 수 있는 문제였습니다...
c++ 은 long long이 9*10^18 정도 까지밖에 표현이 되지 않기 때문에, 이보다 큰 수는 직접 구현을 해주어야 합니다.
 저는 17자리씩 저장하는 1000개의 배열을 만들어 17000자리 수까지 표현할 수 있는 배열을 만들어 이를 구현하였습니다.

 문제풀이는 다음과 같습니다.
(1) (코드: 10~16)
 MOD = 10^17 , F[k] = k번째 피보나치 수 라 할 떄,
 temp[x](=F[x]) = one[x](=F[x-2]) + two[x](=F[x-1]) ; one+two값을 temp 에 저장합니다.
 temp[x](=F[x]) = (one+two)%MOD ( temp[x] 에 x번째 피보나치수의 17자리까지 저장)
 temp[x+1] (=F[x+1]) = (one+two)/MOD ( temp[x+1] 에 x번째 피보나치수의 18자리수를 저장) 해 주었습니다.

(2) (코드: 17~23)
 x번째 피보나치 수 저장 이후, x+1번째 = x-1번째 + x번째 를 계산하기 위해
 one[x+1] = two[x] (=F[x-1]) , two[x+1] = temp[x] (=F[x]) 로 업데이트 해주었습니다.

(3) (코드: 45~54)
 N번째 피보나치 수를 구할 시, 초기 one=0 (= 0번째 피보) , two=1 (= 1번째 피보) 로 설정하고 과정 (1) 을 통해 계산 후, 과정 (2) 를 통해 다음 수를 위해 업데이트 해줍니다.
 N번째 피보나치 수를 구한 뒤는 업데이트 해주지 않습니다.

(4) (코드: 24~42)
 temp 배열에 구해진 피보나치 수를 출력해줍니다.
 10000000000000000000000000000000033 를 출력할때 100000000000000033 으로 중간 '0' 17개가 출력 안되는걸 방지해줍니다.

 매우 큰 수를 어떻게 구현할지가 어려운 문제였습니다.