백준 1735번 분수 합

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

 

아이디어:

1. 두 가지 방식: 최소 공배수를 구해서 먼저 분모를 만들고 계산할 지, 통분하고 합한 뒤에 기약분수로 변경할 지
에서 후자 선택

2. 우선 더하고

3. 분자와 분모의 최대공약수를 따라 나눗셈

4. 최대 공약수에는 유클리드 호제법 사용

5. 유클리드 호제법을 위해 a > b 의 조건으로 수의 크기에 따라 정렬

 

// 1735

#include <iostream>

using namespace std;

int main() {

	ios::sync_with_stdio(false);
	cin.tie(NULL);

	int a, b, c, d, e, f, r;
	
	cin >> a >> b;
	cin >> c >> d;

	e = (a * d) + (b * c);
	f = b * d;

	if (f > e) {
		int tmp = e;
		e = f;
		f = tmp;
	}
	
	while (f != 0) {
		r = e % f;
		e = f;
		f = r;
	}

	int gcd = e;

	e = ((a * d) + (b * c)) / gcd;
	f = (b * d) / gcd;
	
	cout << e << " " << f;

	return 0;
}