문제 링크입니다: 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
지적, 조언, 질문 환영입니다! 댓글 남겨주세요~
'알고리즘 > BOJ' 카테고리의 다른 글
백준 11047번 동전 0 (0) | 2018.02.16 |
---|---|
백준 11727번 2*n 타일링 2 (0) | 2018.02.16 |
백준 1931번 회의실배정 (0) | 2018.02.13 |
백준 11052번 붕어빵 판매하기 (0) | 2018.02.13 |
백준 1010번 다리 놓기 (0) | 2018.02.13 |