백준 6571번 피보나치 수의 개수

문제 링크입니다: https://www.acmicpc.net/problem/6571

백준 2407번 조합(http://jaimemin.tistory.com/682)에서 string을 통해 Big Integer를 구현해 봤기 때문에 문제 자체는 어렵지 않았습니다.

연산자 오버로딩을 통해 string에 대해 <=을 정의해주고 a <= cache[i] && cache[i] <= b인 숫자의 수를 구하면 되는데 함정은 피보나치 수열이 0 1 1 2 3 ... 이런식으로 진행되기 때문에 인덱스를 1부터 for 문을 돌리면 1을 중복해서 세기 때문에 AC를 받을 수 없습니다.

따라서, 인덱스를 2부터 MAX까지 for문을 돌린다면 간단히 AC를 받을 수 있는 문제입니다!

#include <iostream>

#include <string>

#include <algorithm>

using namespace std;

 

const int MAX = 1000;

 

string cache[MAX] = { "0", "1" };

 

string bigNumAdd(string num1, string num2)

{

        long long sum = 0;

        string result;

 

        //1의 자리부터 더하기 시작한다

        while (!num1.empty() || !num2.empty() || sum)

        {

                 if (!num1.empty())

                 {

                         sum += num1.back() - '0';

                         num1.pop_back();

                 }

                 if (!num2.empty())

                 {

                         sum += num2.back() - '0';

                         num2.pop_back();

                 }

                 //다시 string 형태로 만들어 push_back

                 result.push_back((sum % 10) + '0');

                 sum /= 10;

        }

        //1의 자리부터 result에 넣었으므로 뒤집어줘야한다

        reverse(result.begin(), result.end());

        return result;

}

 

//string 연산자 <= 오버로딩

bool operator<=(const string &a, const string &b)

{

        if (a.size() == b.size())

        {

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

                 {

                         if (a[i] > b[i])

                                 return false;

                         else if (a[i] < b[i])

                                 return true;

                 }

                 return true;

        }

        if (a.size() < b.size())

                 return true;

        else

                 return false;

}

 

void preCalculate(void)

{

        for (int i = 2; i < MAX; i++)

                 cache[i] = bigNumAdd(cache[i - 1], cache[i - 2]);

}

 

int main(void)

{

        preCalculate();

 

        while (1)

        {

                 string a, b;

                 cin >> a >> b;

 

                 if (a == "0" && b == "0")

                         break;

 

                 int cnt = 0;

                 for (int i = 2; i < MAX; i++)

                         if (a <= cache[i] && cache[i] <= b)

                                 cnt++;

                 cout << cnt << "\n";

        }

        return 0;

}

개발환경:Visual Studio 2017

지적, 조언, 질문 환영입니다! 댓글 남겨주세요~