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

백준 온라인 저지(BOJ) 1735번 분수 합

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

1735번: 분수 합

* 사용언어 : C언어, C++

 

1. 문제

주어진 두 분수의 합을 기약분수 형태로 구한 후 분자, 분모를 순서대로 출력

 

기약분수는 더 이상 약분되지 않는 분수를 의미하고

입력은 n1의 분자, n1의 분모, n2의 분자, n2의 분모 순서로 주어짐

 

2. 풀이

입출력 예시가 약간 헷갈릴 수 있는데

해석해보면 아래와 같은 의미인 것을 알 수 있습니다.

따라서 같은 절차로 분자(A)와 분모(B)를 구하면 됩니다.

 

다만 입력 예시의 경우 계산된 결과가 이미 기약분수이기라서 따로 처리하지 않아도 되지만

다른 입력에서는 기약분수가 될 수 있습니다.

 

일반적인 분수에 대해서 분자와 분모의 최대공약수를 구한 후 각각 나눠주면 기약분수가 됩니다.

이를 활용하여 기약분수를 구하고 출력하면 됩니다.

 

3. 코드

#ifndef _CRT_SECURE_NO_WARNINGS
#define _CRT_SECURE_NO_WARNINGS
#endif
/*
1735_분수 합
1112KB	0ms
*/
#include <cstdio>

int gcd(int a, int b) {
	int t, r;

	if (a < b) {
		t = a;
		a = b;
		b = t;
	}

	while (1) {
		r = a % b;
		if (r == 0) break;
		a = b;
		b = r;
	}
	return b;
}

int main() {
#ifdef _WIN32
	freopen("input.txt", "r", stdin);
#endif // _WIN32
	int n1a, n1b, n2a, n2b, a, b, g;
	scanf("%d %d %d %d", &n1a, &n1b, &n2a, &n2b);

	a = n1a * n2b + n2a * n1b;
	b = n1b * n2b;
	g = gcd(a, b);

	printf("%d %d\n", a / g, b / g);
	return 0;
}

* a, b 크기 비교를 미리 할 경우 분자, 분모가 바뀌기 때문에 gcd 함수 안에서 처리했습니다. (value copy이므로 영향 X)