[BOJ][C++] 백준 1735번: 분수 합 (Silver III)

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

 

문제

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

입력

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

출력

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

 

풀이

// 풀이 : https://whkakrkr.tistory.com

#include <iostream>
#include <vector>
#include <set>

using namespace std;

// 최대공약수
int getGcp(int a, int b) {
    return a==0 ? b : getGcp(b%a, a);
}

// 최소공배수
int getLcm(int a, int b) {
    int gcp = getGcp(a, b);
    return a*b/gcp;
}

// 약분
void getReduced(int &ja, int &mo) {
    int gcp = getGcp(ja, mo);
    ja /= gcp;
    mo /= gcp;
}

int main() {
    ios_base::sync_with_stdio(false);
	cout.tie(NULL);
	cin.tie(NULL);
	
	int a,b,c,d;
	cin >> a >> b >> c >> d;
	
    // (1) 각 분수 약분하기
	getReduced(a,b);
	getReduced(c,d);
	
    // (2) 통분하기
	int lcm = getLcm(b,d);
	a *= lcm/b;
	c *= lcm/d;
	
    // (3) 더하기
	int ja = a+c;
	int mo = lcm;
    
    // (4) 더해서 나온 분수 약분
	getReduced(ja, mo);
	
	cout << ja << " " << mo;
	
    return 0;
}