[백준 C++] 1735 분수 합 - 유클리드호제법

1735번: 분수 합

#include <iostream>
using namespace std;

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

	int A, B;
	cin >> A >> B;

	int C, D;
	cin >> C >> D;

	int Child, Parent;
	if (B == D)
	{
		Child = A + C;
		Parent = B;
	}
	else
	{
		Child = A * D + C * B;
		Parent = B * D;
	}

	int X = max(Child, Parent);
	int Y = min(Child, Parent);
	int Z;
	while (Y != 0)
	{
		Z = X % Y;
		X = Y;
		Y = Z;
	}

	Child /= X;
	Parent /= X;

	cout << Child << ' ' << Parent;
}

---

 

유클리드 호제법을 이용해서 분자와 분모의 최대 공약수를 구한 후

해당 분수를 최대공약수로 나눠주어 기약 분수로 나타내도록 하는 문제입니다.

 

유클리드 호제법을 이용해서 두 수의 최대 공약수를 구하는 과정은 다음과 같습니다.

 

1. 큰 수를 작은 수로 나누는 MOD 연산 수행
2. 앞 단계에서의 작은 수와 MOD 연산 결과(나머지)로 MOD 연산 수행
3. 단계 2를 반복하다가 나머지가 0이 되는 순간의 작은수 = 최대 공약수