백준 1735번 C++

백준 1735번 분수 합

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

1735번: 분수 합

정답 코드

#include <iostream>
#include <string>
using namespace std;
int GCD(int, int);
int main()
{
	int numerator, denominator;
	int numerator1, denominator1;
	int numerator2, denominator2;
	int gcd;

	cin >> numerator1 >> denominator1;
	cin >> numerator2 >> denominator2;

	if (denominator1 == denominator2)
	{
		numerator = numerator1 + numerator2;
		denominator = denominator1;
	}
	else
	{
		numerator = (numerator1 * denominator2) + (numerator2 * denominator1);
		denominator = denominator1 * denominator2;
	}

		gcd = GCD(denominator, numerator);
		cout << numerator / gcd <<" "<< denominator / gcd << endl;

	return 0;
}
int GCD(int B, int A)
{
	if (B % A == 0)
		return A;
	else
		return GCD(A, B%A);
}

문제 풀이

기약분수에 관한 문제입니다. 이를 해결하기 위해서는
일반적인 분수 덧셈과정에서의 통분, 그리고 나서 최대공약수를 통한 약분을 하는 문제입니다. 다만 최대공약수를 구하기 위해서는 유클리드 호제법이라는 알고리즘을 사용해야 합니다.
유클리드 호제법이란 A=bq+r일때
GCD(A,B)=GCD(q,r)입니다.
G가 A와b의 약수라면 동시에 G는 A-B의 약수입니다.
또한 A를 b로 나눴을 때 나머지가 r이라면
A와 b의 최대공약수는 b와 r의 최대공약수입니다.
더 자세한 건 여기를 클릭해보세요
.