[코딩문제]n번째 피보나치 나머지 구하기 - 2

#include <iostream>

using namespace std;

/*

피보나치 수열이란,

첫 번째 항의 값이 0이고 두 번째 항의 값이 1일 때,

이후의 항들은 이전의 두 항을 더한 값으로 이루어지는 수열을 말한다.

예) 0, 1, 1, 2, 3, 5, 8, 13

피보나치 수열의 n번째 수를 4,294,967,291으로 나누었을 때의

나머지를 출력하는 프로그램을 작성하시오.

정수 n이 입력으로 주어진다. (1 <= n <= 10^100000)

*/

#define MAXNUM 4294967291 //unsigned int 최대인 4294967295 보다 4 작음

unsigned int first = 0;

unsigned int second = 1;

int fibonacciCount = 0; //숫자 1, 2, 그외 체크용 카운트

//피보나치 계산 함수

unsigned int Fibonacci()

{

fibonacciCount++;

//cout << fibonacciCount << "번째";

if (fibonacciCount == 1) return first;

else if (fibonacciCount == 2) return second;

else if (fibonacciCount > 2)

{

fibonacciCount--; //카운트를 3이상 늘릴 필요는 없다

unsigned int temp = 0;

temp = first;

first = second;

if (MAXNUM - second < temp)

{

second = temp - (MAXNUM - second);

}

else

{

second += temp;

}

return second;

}

}

//0 체크 함수

bool NumIsZero(char* numChar, int size)

{

int count = 0;

for (int i = 0; i < size; i++)

{

if (*(numChar + i) == '0')

{

count++;

}

else

{

break;

}

}

if (count == size)

{

return true;

}

else

{

return false;

}

}

//숫자 -1 시키는 함수

void NumMinus(char* numChar, int size)

{

int idx = size - 1;

while (!NumIsZero(numChar, size)) //숫자가 0이 아니라면

{

if (*(numChar + idx) != '0') //자릿수가 0이 아니라면 

{

*(numChar + idx) = *(numChar + idx) - 1; //1 빼주고 나옴

break;

}

else

{

*(numChar + idx) = '9'; //자릭수가 0이면 9로 바꾸어 주고

idx--; //다음 자릿수를 찾기로 함

}

}

}

void main()

{

char n[256];     //숫자를 넣을 char 배열 - 높은 숫자를 하기 위해선 자리수만큼 더 늘려야 한다

cin >> n; //입력

char* charTemp = n;

while (*charTemp != '\0')

{

charTemp++;

}

int  charSize = charTemp - n;    //들어온 수의 사이즈

while (!NumIsZero(n, charSize))

{

cout << n << endl;        //진행도를 알기 위한 출력

NumMinus(n, charSize);

Fibonacci();

}

cout << endl << second << endl;

getchar();

getchar();

}

어제 했었던 문제와 같은 문제이다.

하지만 어제 무시했었던 10^100000을 처리하기 위해

char배열로 n값을 받고 char배열에 있는 값을 변환하여 처리하도록 하였다.

메모리 공간을 256이 아니라 더 많이 늘리면 자료형의 최대값(맥스값)보다 더 큰 값도 구하는 것이 가능하다.

이 코딩에는 큰 문제가 하나 발생하는데 

엄청 느리다

숫자를 char배열로 하나하나 컨트롤 하니 느리다곤 생각하고 있었지만

느려도 너무 느리다.

1000000000000000(1천조)를 처리하는데 대략 10개월 정도의 시간이 걸릴것 같다.

이런 프로그램을 짜서는 안되겠지만

그래도 짤려면 이렇게라도 짤 수 있단걸 보여주기 위해 해보았다.

문제 출처 : 코딩도장

코딩 출처 : 내 머리, 내 손