(백준/C++) 1735_분수합

1735번:분수 합 (acmicpc.net) 문제는 단순히 두 분수를 입력 받아 합한 다음에 기약분수로 만드는 문제입니다.

다만, 기약분수로 만들 때, 분자와 분모의 최대 공약수(GCD)를 구하고 이를 이용하면 됩니다.

최대 공약수(GCD)는 아래 글에서 확인할 수 있습니다.

유클리드 호제법과 최대 공약수(GCD), 최소 공배수(LCM)

풀이

이 문제는 단순히 분수 두 개만 입력 받으니 그에 대한 입력만 받으면 됩니다.

두 분수의 합은 다음과 같이 구할 수 있습니다.

\[\frac{A}{B} + \frac{C}{D} = \frac{A \times D + B \times C}{B \times D}\]

또한, 합해진 분수를 기약분수로 만들기 위해, 분자와 분모의 최대공약수(GCD)를 구하고, 이를 사용하여 분자와 분모를 나눕니다.

#include <cstdio>

int GCD(int a, int b)
{
	while (b != 0)
	{
		int r = a % b;
		a = b;
		b = r;
	}
	return a;
}

int main()
{
	int c1, p1, c2, p2, c, p;
	scanf("%d %d %d %d", &c1, &p1, &c2, &p2);

	p = p1 * p2;
	c = c1 * p2 + c2 * p1;

	int gcd = GCD(c, p);

	printf("%d %d", c / gcd, p / gcd);
}

---

참고

유클리드 호제법과 최대 공약수(GCD), 최소 공배수(LCM)