[BOJ/Silver 3] 백준 1735 분수 합(C++)

문제 링크

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

1735번: 분수 합

 

문제

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

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

입력

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

출력

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

예제 입력 1

2 7
3 5

예제 출력 1

31 35

알고리즘 분류

• 수학

풀이

유클리드 호제법을 사용한다.

분모 2개의 최소공배수를 구하고 최소공배수로 분모를 통일한다. 그리고 두 분수의 합을 구하고, 다시 분자와 분모의 최대공약수를 구해서 약분해준다. 약분 안 하면 정답 처리가 되지 않으니 주의해야 한다.

코드

#include <iostream>
#include <string>
#include <vector>
#include <algorithm>
#include <cmath>
#define FASTIO cin.tie(NULL); cout.tie(NULL); ios::sync_with_stdio(false);

using namespace std;
int A[3], B[3];

int GCD(int N, int M) {
	while (1) {
		int R = N % M;
		if (R == 0) {
			return M;
		}
		N = M;
		M = R;
	};
}

int LCM(int N, int M) {
	return (N * M) / GCD(N, M);
}

void Input() {
	for (int i = 0; i < 2; i++) {
		cin >> A[i] >> B[i];
	}
}

void Settings() {
	if (B[0] < B[1]) {
		swap(A[0], A[1]);
		swap(B[0], B[1]);
	}
	int L = LCM(B[0], B[1]);
	A[0] *= (L / B[0]);
	A[1] *= (L / B[1]);
	A[2] = A[0] + A[1];
	B[2] = L;
	int G = GCD(B[2], A[2]);
	A[2] /= G;
	B[2] /= G;
}

void Find_Answer() {
	cout << A[2] << " " << B[2] << "\n";
}

int main() {
	FASTIO
	Input();
	Settings();
	Find_Answer();

	return 0;
}