[백준] 1735 분수 합 (C++)

 

입출력

 

 

 

 

 

---

풀이

 

 

#include<iostream>

using namespace std;

int gcd(int child, int parent)
{
    int r = child % parent;

	if (r == 0)
        return parent;
    else
        return gcd(parent, r);

}

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

    int a, b, c, d;
    cin >> a >> b;
    cin >> c >> d;

    int child, parent;
    child = (a * d) + (b * c);
    parent = b * d;

    int gcdNum;
    gcdNum = gcd(child, parent);

    child  /= gcdNum;
	parent /= gcdNum;

    cout << child << " " << parent;

    return 0;
}

 

 

유클리드 호제 법

 

유클리드 호제법은 최대공약수를 구하는 방법이다

두 양의 정수 a, b (a > b) 에 대하여 a = bq + r (0 <= r < b)라면, a,b의 최대공약수는 b,r의 최대공약수와 같다

 

즉 , r = 0이라면 a,b의 최대공약수는 b가 된다

 

이 방법을 사용하여 gcd()함수 _ 최대공약수를 구하는 함수_를 만들었다