[백준 1735번] 분수 합

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

분수 합 성공

시간 제한	메모리 제한	제출	정답	맞은 사람	정답 비율
2 초	128 MB	7265	3012	2555	43.298%

문제

분수 A/B는 분자가 A, 분모가 B인 분수를 의미한다. A와 B는 모두 자연수라고 하자.

두 분수의 합 또한 분수로 표현할 수 있다. 두 분수가 주어졌을 때, 그 합을 기약분수의 형태로 구하는 프로그램을 작성하시오. 기약분수란 더 이상 약분되지 않는 분수를 의미한다.

입력

첫째 줄과 둘째 줄에, 각 분수의 분자와 분모를 뜻하는 두 개의 자연수가 순서대로 주어진다. 입력되는 네 자연수는 모두 30,000 이하이다.

출력

첫째 줄에 구하고자 하는 기약분수의 분자와 분모를 뜻하는 두 개의 자연수를 빈 칸을 사이에 두고 순서대로 출력한다.

예제 입력 1 

2 7
3 5

예제 출력 1 

31 35

유클리드 호제법을 이용한 최소 공배수, 최대 공약수를 찾아서 푸는 문제이다.

유클리드 호제법은 짧게 구현이 가능하니 연습하자.

#include<iostream>
#include<algorithm>
using namespace std;
 
int a,b,c,d;
 
int gcd(int a, int b){
    return b ? gcd(b, a % b) : a;
}
 
int lcm(int a, int b){
    return a * b / gcd(a,b);
}
 
int main(){
 
    cin >> a >> b >> c >> d;
 
    if(b < d){
        swap(a,c);
        swap(b,d);
    }
 
    int lcm_num = lcm(b,d);
 
    a = a * (lcm_num/b) + c * (lcm_num/d);
    b = gcd(a,lcm_num);
 
    cout << a / b << " " << lcm_num / b;
 
    return 0;
}