백준 1735번 분수 합 풀이

문제

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

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

입력

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

출력

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

 

해당문제는 유클리드 호제법을 이용하여 풀었다.

유클리드 호제법은 최소공배수 = 수1* 수2 / 최대공약수 다. 근데 다 두 분수를 합친 후에도 한번 더 기약분수를 만들어줘야하는 부분을 깜빡해서 조금 애를 먹었다.

#include <iostream>
#include <set>

using namespace std;

int n1(0), m1(0);
int n2(0), m2(0);
int mini(0), value(0);
int answerSun(0), answerPar(0);


int findGcd(int a, int b)
{
	const int remainder = a % b;
	if (remainder == 0)
		return b;

		return findGcd(b, remainder);
}



int main()
{
	cin >> n1 >> m1;
	cin >> n2 >> m2;

	mini = findGcd(m1, m2);

	value = m1* m2 / mini;

	answerSun = (n1 * (value / m1)) + (n2 * (value / m2));
	answerPar = value;
	mini = 10;
	while(mini!=1)
	{
		mini = findGcd(answerSun, answerPar);
		answerSun /= mini;
		answerPar /= mini;
	}

	cout << answerSun << " " << answerPar << "\n";
	
	return 0;
}