[C++/ 백준 1735번] 분수 합

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

1735번: 분수 합

 

해결 방법

 

유클리드 호제법을 사용했다.

1. 분모끼리 곱해서 우선 약분이 가능하거나 가능하지 않은 한 개의 분수로 만든다.
2. 구해진 분자와 분모를 이용해 유클리드 호제법을 적용하면 최대공약수를 구할 수 있다.(당연히 1일 수 있다)
3. 최대공약수로 분자와 분모를 나누어 주면 끝.

정말 간단했는데... 새삼 알고리즘 구상의 중요성을 느낀다. 턱을 괴고 생각하는 시간을 더 늘려야겠다.  

 

 

#include <iostream>
#include <algorithm>
using namespace std;
long long int max_div;
long long int min_mul;
long long int A, AS, B, BS;

long long int euclid(long long int a, long long int b)
{
   
    if (a % b != 0)
    {
        return euclid(b, a % b);
    }
    else
    {
        return b;
    }
}


int main()
{
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    cout.tie(nullptr);
  
        cin >> AS >> A;
        cin >> BS >> B;

        long long int num;
   
        long long int cnt = 0;

        long long int max_div = euclid((A < B ? A : B), (A > B ? A : B));
        
       long long int S, M;

   

        S = AS * B + BS * A;
        M = A * B;

        if (S < M)
        {
            max_div = euclid(M, S);
        }
        else if (S > M)
        {
            max_div = euclid(S, M);
        }
        else
        {
            cout << "1 1";
            return 0;
        }

        cout << S / max_div << ' ' << M / max_div;


     

    return 0;
}