[백준 1735번][C++] 분수 합

<문제 소개>

---

<소스 코드>

#include <iostream>
#include <string>
#include <vector>
#include <sstream>
#include <map>
#include <unordered_map>
#include <set>
#include <cmath>
#include <stack>
#include <queue>
#include <algorithm>
#include <cstdlib>
using namespace std;

int gcd(int big, int small)
{
	// 유클리드 호제법
	int r = big % small; // 나머지

	if (big % small == 0) return small;
	else return gcd(small, r);
}

int main()
{
	// 쓰레드 환경이 아닐때 버퍼를 분리하여 처리속도를 빠르게 해줌
	ios_base::sync_with_stdio(false);
	cin.tie(NULL);
	cout.tie(NULL);

	int A, B, C, D;
	cin >> A >> B >> C >> D;

	int x = (A * D) + (C * B); // 분자
	int y = B * D; // 분모

	int GCD; // 분자, 분모의 최대공약수

	if (x > y)
	{
		GCD = gcd(x, y); 
	}
	else
	{
		GCD = gcd(y, x); 
	}

	cout << x / GCD << " " << y / GCD;

	return 0;
}

---

<풀이과정>

1. 각각의 분자, 분모의 값인 (A,B), (C,D)를 입력 받음

2. 분모를 통일하여 두 분수의 합을 구한 뒤 해당 분수를 기약분수로 만들어야함

3. 그렇기에 분수의 합의 분자인 x는 각 분자에 상대 분모를 곱한 값을 더해서 구함 x = (AxD) + (CxB)

4. 또한 분모 y는 두 분모를 곱한 값이 됨 y = BxD

5. 이제 더한 값의 분자, 분모를 구하였으므로 두 수의 최대공약수를 구해 각각을 나누어주어야 함

6. 유클리드 호제법을 이용해 최대공약수를 구함

7. 두 수 중 큰 수를 작은 수로 나눈 나머지가 0이면 둘 중 작은 수가 최대공약수가 되고, 나머지가 0이 아니라면 큰 수에 현재 작은 값을, 작은 수에는 나머지 값을 넣어서 같은 과정을 나머지가 0이 나올때까지 반복한다.

8. 위의 과정을 통해 구한 최대공약수를 이용해 분자, 분모를 각각 나누어서 나온 값을 출력한다.

---

<코멘트>

기약분수는 분자, 분모의 최대공약수로 각각을 나눠주면 되므로 유클리드 호제법을 이용해 최대공약수를 구해 나누어서 구해주었다.

---

<제출결과>