[C/C++] 백준 - 1735번 : 분수 합

문제

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

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

입력

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

출력

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

---

Step 1.

두 분수가 주어지면 그 분수의 합을 표현한다.

 

Step 2.

합으로 표현된 하나의 분수를 기약분수 형태로 바꿔준다.

 

기약분수 형태로 바꾸는 것이 이 문제에서 요구하는 문제 해결 능력인 것 같다.

 

나는 무한 반복문 형태로 2부터 분수와 분모 중 더 작은 값보다 큰 값이 될 때 까지 모든 수를 확인해보며 진행하였다.

 

만약 해당 수로 분모와 분자 모두 약분이 가능할 때 약분을 진행해주었다. 그리고 다시 위 과정을 2부터 진행한다.

 

만약 2부터 시작해서 분모/분자 중 더 작은 값보다 클 때까지 진행할 경우 기약분수라는 것을 의미한다.

 

#include <bits/stdc++.h>
#define fastio ios::sync_with_stdio(false), cin.tie(0), cout.tie(0)

using namespace std;

int n1, n2, v1, v2;

void input() {
	cin >> n1 >> n2 >> v1 >> v2;
}

void solution() {
	int down = n2 * v2;
	int up = (n1 * v2) + (n2 * v1);

	int std = down > up ? up : down;
	int index = 2;
	while (1) {
		std = down > up ? up : down;
		if (index > std) break;

		if (down % index == 0 && up % index == 0) {
			up /= index;
			down /= index;
			index = 2;
		}
		else {
			index++;
		}
	}
	cout << up << " " << down << endl;
}

int main() {
	fastio;
	input();
	solution();

	return 0;
}