#1735

• 문제

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

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

• 코드

#include <iostream>
#include <vector>

using namespace std;

int gcdIter(int a, int b) {//최대 공약수 구하는 함수
	while (b) {
		a %= b;
		swap(a, b);
	}
	return a;
}

vector<int> addFountain(vector<int>& n1, vector<int>& n2) {
	vector<int> result; //두 분수를 더한 값
	int gcd;
	result.assign(2, 0);
	//분모의 최소 공배수 구하기
	gcd = gcdIter(max(n1[1], n2[1]), min(n1[1], n2[1]));
	result[1] = n1[1] * n2[1] / gcd; //공통 분모 구하기

	//두 분수를 더한 분수의 분자 구하기
	n1[0] *= result[1] / n1[1];
	n2[0] *= result[1] / n2[1];
	result[0] = n1[0] + n2[0];

	//기약 분수인지 확인 
	int i = gcdIter(max(result[0], result[1]), min(result[0], result[1]));
	if (i != 1) { //기약 분수가 아니면
		result[0] /= i;
		result[1] /= i;
	}

	return result;
}

int main()
{
	vector<int> n1; // 첫번째 분수
	vector<int> n2; // 두번째 분수
	vector<int> result; //두 분수를 더한 분수
	n1.assign(2, 0);
	n2.assign(2, 0);

	//입력
	cin >> n1[0] >> n1[1];
	cin >> n2[0] >> n2[1];

	//연산
	result = addFountain(n1, n2);
	
	//출력
	cout << result[0] << " " << result[1];

	return 0;

}

• 해설

1. gcdIter 함수 

- 최대 공약수를 구하는 함수

 

2. addFountain 함수

- 두 분수를 더하는 함수

: gcdIter 함수를 이용해 각 분수의 분자, 분모를 받아온 벡터 n1 , n2에서 분모의 최대 공약수를 구함

: 두 분모의 곱을 최대 공약수로 나누어 최소 공배수를 구해 공통 분모를 구함

: 두 분수의 분자를 공통 분모에 맞는 분자로 만들어주기 위해 공통분모에 각 분모를 나눈 값을 분자에 곱해줌

: 그렇게 구한 분자를 더해서 result의 분자 값에 넣어줌

: 기약분수인지 확인하기 위해 result의 분모와 분자의 최대공약수를 구함

: 만약 최대 공약수가 1이 아니라면 기약 분수가 아니므로 각 분모와 분자를 최대공약수로 나누어주어 기약분수로 만들어 줌

: result 벡터를 return 함

 

3. main 함수

: 두 분수를 n1, n2 에 입력 받고 addFountain 함수를 이용해 두 분수를 더한 값을 result에 저장함