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

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

문제

---

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

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

 

입력

---

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

 

출력

---

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

 

문제 풀이

---

유클리드 호제법을 이용한 문제.

두 분수 A/B + C/D를 계산하면 (AD+BC) / BD이다. 따라서 우리는 AD+BC와 BD가 서로소인지 판별해주고, 아니라면 공통의 인수로 계속 나누어 기약분수를 만들어주면 된다. 서로소인지 판별은 유클리드 호제법을 이용해 구할 수 있다. 두 수의 최대공약수가 1이라면 서로소이고, 아니라면 분자와 분모를 최대공약수로 나누어주면 기약분수를 만들 수 있다.

 

아래는 코드.

#include <iostream>
using namespace std;

int GCD(int x, int y)
{
	if (y == 0)
	{
		return x;
	}
	else
	{
		return GCD(y, x % y);
	}
}

int main()
{
	cin.tie(NULL);
	ios::sync_with_stdio(false);

	int A, B, C, D;
	cin >> A >> B;
	cin >> C >> D;
	int numerator = A * D + B * C;
	int denominator = B * D;
	while (GCD(numerator, denominator) != 1)
	{
		int gcd = GCD(numerator, denominator);
		numerator /= gcd;
		denominator /= gcd;
	}
	cout << numerator <<" " << denominator << "\n";
	return 0;
}