백준 4587번 이집트 분수

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

codewars의 Some Egyptian fractions(http://jaimemin.tistory.com/395?category=987931) 문제를 푼 다음 비슷한 문제가 있어서 풀어봤습니다.

직접 테스트 케이스를 입력하고 컴파일을 하면 맞게 나오는데 어디가 틀린건지 도무지 모르겠습니다.

혹시 틀린 부분이 있다면 댓글을 통해 알려주시면 정말 감사하겠습니다!

#include <iostream>

#include <vector>

#include <algorithm>

using namespace std;

 

const int MAX = 1000000;

 

vector<long long int> v;

 

//최대공약수

long long int gcd(long long int N, long long int D) //greatest common denominator

{

        if (D == 0)

               return N;

        return gcd(D, N%D);

}

 

void egyptianFraction(long long numerator, long long denominator)

{

        while (1)

        {

               //주석까지 추가하면 메모리 초과

               /*

               if (denominator%numerator == 0) //분자가 분모로 나누어진다면

               {

                       v.push_back(denominator / numerator);

                       return;

               }

               if (numerator%denominator == 0) //분수가 아니라 양의 정수라면

               {

                       v.push_back(numerator / denominator);

                       return;

               }

               if (numerator > denominator) //분자가 분모보다 큰 경우(대분수로 만듬)

               {

                       v.push_back(numerator / denominator);

                       numerator %= denominator;

                       continue;

                }

               */

               //(분자/분모)의 upper_bound

               long long int newDenominator = (denominator / numerator);

               if ((denominator%numerator) != 0) //분자가 분모로 나누어지지 않는다면

                       newDenominator++;

               //이집트 분수의 공식(다음 피제수와 제수)

               long long int nextNumerator = (numerator*newDenominator) - denominator;

               long long int nextDenominator = newDenominator*denominator;

               //조건에 unit fraction이 1000000을 넘으면 안된다고 했으므로 조건을 충족하는지 검사

               long long int tempN = nextNumerator / gcd(nextDenominator, nextNumerator); //임시 피제수

               long long int tempD = nextDenominator / gcd(nextDenominator, nextNumerator); //임시 제수

               if (tempD >= MAX) //조건 만족 안될시

               {

                       while (1)

                       {

                              newDenominator++;

                              //이집트 분수의 공식 다시 계산

                              nextNumerator = (numerator*newDenominator) - denominator;

                              nextDenominator = newDenominator*denominator;

                              //조건 충족하는지 다시 확인

                              tempN= nextNumerator / gcd(nextDenominator, nextNumerator);

                              tempD = nextDenominator / gcd(nextDenominator, nextNumerator);

                              if (tempD < MAX)

                                      break;

                       }

               }

               v.push_back(newDenominator);

               numerator = nextNumerator;

               denominator = nextDenominator;

               if (numerator == 0)

                       break;

        }

        return;

}

 

int main(void)

{

        while (1)

        {

               v.clear();

               long long int numerator, denominator;

               cin >> numerator >> denominator;

               if (numerator == 0 && denominator == 0)

                       break;

               egyptianFraction(numerator, denominator);

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

                       cout << v[i] << " ";

               cout << endl;

        }

        return 0;

}

개발환경:Visual Studio 2017

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