BOJ - 분수 합 (1735번)

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

 

최대공약수, 최소공배수 혼합 문제였다.

 

접근방법

1. 분모의 최소공배수를 구해서 lcd라고 하자.

2. 분모를 lcd로 통분할건데, 분모먼저 바꾸면 안된다. 분자 먼저 바꿔야 한다.

3. 분자 * (lcd/분모) 해서 분자 통분.

4. 분모 * (lcd/분모) 해서 분모 통분.

5. 통분 끝났으니 분자의 합을 구하자. 변수 만들어서 합을 저장.

6. 분자의 합과 분모의 최대공약수를 구하자.

7. 분자의 합과 분모의 합을 최대공약수로 나누어 기약분수 형태로 만든 뒤 출력

 

전체 코드

#include <iostream>
#include <stack>
#include <string>
#include <unordered_map>
#include <vector>
#include <algorithm>
using namespace std;
typedef long long int ll;
ll getLcd(ll max, ll min); // 최소공배수 구하는 함수
ll getGcd(ll max, ll min); // 최대공약수 구하는 함수
int main() {
	ios_base::sync_with_stdio(false);
	cin.tie(NULL);
	// a / b
	// c / d
	int a, b, c, d, sumOfNumerator, gcd;
	cin >> a >> b >> c >> d;
	// 1. 분모의 최소 공배수 구하기
	int lcd = getLcd(max(b, d), min(b, d));
	// 2. 각 분자를 분모에 곱해진 수 만큼 똑같이 곱해주기
	a = a * (lcd / b); 
	c = c * (lcd / d);
	// 3. 분자를 최소공배수만큼 바꿔주기
	b = b * (lcd / b);
	d = d * (lcd / d);
	// 4. 분자의 합 구하기
	sumOfNumerator = a + c;
	// 5. 분자와 분모의 최대공약수 구해서 분자와 분모 나누기
	gcd = getGcd(sumOfNumerator, b);
	cout << sumOfNumerator / gcd << ' ' << b / gcd;
	return 0;
}
ll getLcd(ll max, ll min) {
	ll a = max, b = min, tmp, gcd;
	while (b != 0)
	{
		tmp = a;
		a = b;
		b = tmp % b;
	}
	gcd = a;
	return max * min / gcd;
}
ll getGcd(ll max, ll min) {
	ll a = max, b = min, tmp;;
	while (b != 0)
	{
		tmp = a;
		a = b;
		b = tmp % b;
	}
	return a;
}