[백준/C++] 4587번 이집트 분수

https://www.acmicpc.net/problem/4587

4587번: 이집트 분수

이 문제 역시 알고리즘 수업에 나온 문제가 백준에 있길래 풀어보았다.

내가 아는 이집트 분수의 풀이법은 2가지다.

1. 현재 분수에서 뺄 수 있는 가장 큰 기약분수로 빼면서 구하기

2. 현재 분수 p/q를 뒤집어서 q/p로 만든 후, 이 q/p보다 큰 정수를 선택하고, 그 정수를 역을 취해 원래 분수에 빼주는 방법

2번 방법이 시간적인 측면에서 훨씬 유리하기 때문에, 2번으로 해보려다가 문제의 조건을 보고 1번 방법을 택했다. ( 모든 분수의 분모가 1,000,000이 넘지 않아야 하며, 3/999983과 같은 분수가 1/999983 + 1/999983 + 1/999983으로 나눠지는 것 때문이다.)

원래 이집트 분수 계산에 의하면 3/999983 = 1/333328 + 1/333322333424 이다!

문제를 풀어보겠다.

1. 우선, m=2로 설정한 뒤, 입력으로 주어진 분수와 기약분수의 대소를 비교한다. (=> cmp함수)

2. 만약 뺄셈이 가능하다면, 분수의 뺄셈을 진행한 뒤 최대공약수 구하는 함수( => gcd함수) 를 이용해 최대공약수를 구해준다.(통분하기 위해서) 그리고 뺄셈을 진행한 기약분수를 벡터에 저장해준다.

3. 근데 뺄셈과 통분을 진행한 분수의 분모가 백만보다 크다면 이 기약분수는 쓸 수 없으므로 벡터에 저장한 것을 지워준다.

4. 그리고 뺄셈과 통분을 진행한 분수가 기약분수라면 이집트 분수를 전부 구한 것이므로 결과를 저장해주고 while문을 종료한다.     

5. 만약, 아직 더 뺄셈을 진행할 수 있다면 p,q를 새로 계산한 값으로 업데이트해준다. (m을 1줄이는 이유는 앞서 말했듯 3/999983과 같은 분수가 1/999983 + 1/999983 + 1/999983과 같이 똑같은 분모를 가진 채 나눠지는 것 때문이다.)

#include<bits/stdc++.h>
using namespace std;
typedef long long ll;

ll gcd(ll x, ll y) {
    ll buf,res;
    if(x<y){
        buf = x;
        x = y;
        y = buf;
    }
    while(y!=0){
        res = x%y;
        x = y;
        y = res;
    }
    return x;
}

void egyptianFraction(ll p, ll q) {
    vector<ll> v;
    int cnt = 1000000;
    ll m=2;

    while(cnt--) {
        if (cmp(p,q,m)) { // 단위 분수로 빼기
            ll bunmo = q * m;
            ll bunza = (p * m) - (1 * q);
            ll tmp = gcd(bunza, bunmo);
            v.push_back(m);
            if(bunmo/tmp >= 1000000){
                v.pop_back();
            }
            else if (bunza / tmp == 1) { // 단위분수를 뺀 결과가 단위분수이고, 분모가 백만보다 작다면
                v.push_back(bunmo/tmp);
                break;
            }
            else if(bunza/tmp != 1){ // 단위 분수를 뺀 결과가 단위분수가 아니라면
                p = bunza/tmp; q = bunmo/tmp;
                m--;
            }
        }
        m++;
    }
    for(int i=0; i<v.size();i++){
        cout << v[i]<< ' ';
    }
    cout << '\n';
}

int main() {
    ios_base::sync_with_stdio(false);
    cin.tie(nullptr);
    cout.tie(nullptr);

    ll p, q;
    while(true) {
        cin >> p >> q;
        if (p == 0 && q == 0) break;
        egyptianFraction(p, q);
    }
    return 0;
}