백준 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개가 출력 안되는걸 방지해줍니다.

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

	#include <bits/stdc++.h>
	using namespace std;
	const long long MOD = 1e17;
	const int MAX = 1000;
	typedef long long ll;
	int n;
	// 17자리씩 1000개의 배열 17000 자리까지 표현 가능
	long long int one[MAX+1], two[MAX+1], temp[MAX+1];
	void Plus(){
	for (int i = 0; i < MAX; ++i){
	ll tt = one[i]+two[i];
	temp[i] += tt%MOD;
	temp[i+1] += tt/MOD;
	}
	}
	void Update(){
	for (int i = 0; i < MAX; ++i){
	one[i] = two[i];
	two[i] = temp[i];
	temp[i] = 0LL;
	}
	}
	void Print(){
	bool start = false;
	for (int i = MAX; i >=0; i--){
	if(temp[i]!=0LL || start){
	if(!start){
	start = true;
	cout << temp[i];
	}
	// 출력해야 되는 수가 10000000000000000000000000000000033 인 경우
	// 100000000000000033 으로 중간 '0' 17개가 출력 안되는걸 방지
	else{
	cout.width(17);
	cout.fill('0');
	cout<<temp[i];
	}
	}
	}
	cout << '\n';
	}
	int main(){ios_base::sync_with_stdio(false); cout.tie(NULL); cin.tie(NULL);
	cin >> n;
	if(n==0) cout << 0 << '\n';
	else if (n==1) cout << 1 << '\n';
	else{
	two[0] = 1LL;
	for (int i = 2; i <= n; ++i){
	Plus();
	if(i!=n) Update();
	}
	Print();
	}
	return 0;
	}

view raw BOJ 10826.cpp hosted with ❤ by GitHub