[Baekjoon] 1735번: 분수 합

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

1735번: 분수 합

 

---

 

문제 해결 과정

착안

분모가 다른 두 분수 \(A, B\)의 계산을 위해 두 수를 통분(reduction to common denominator, 영어로는 별도로 통분을 나타내는 하나의 용어가 존재하지 않는다)하여 계산하고, 기약분수(irreducible fraction)로 나타내기 위해 최종 계산된 분자와 분모 사이의 최대공약수(greatest common divisor, GCD)를 구해 분자와 분모를 약분(reduction of a fraction)한다.

 

구현

어차피 계산 과정에서 마지막에 기약분수로 나타내는 과정에서 분자와 분모 사이의 최대공약수를 반드시 한 번 구해야 하므로, 굳이 최대공약수를 두 번(통분할 때 분모들 사이의 최대공약수 한 번, 약분할 때 분자와 분모 사이의 최대공약수 한 번) 구하지 않기 위해 공통분모를 두 분수의 분모 사이의 최소공배수(least common multiplier, LCM)로 하지 않고 그냥 두 분수의 분모의 곱으로 계산하였다.

 

[스포 주의] 아래 '더보기'를 누르면 코드가 나오니 주의하세요~

#include <iostream>

using namespace std;

int GCD(int a, int b)
{
	while (b)
	{
		int r = a % b;
		a = b;
		b = r;
	}
	return a;
}

int main()
{
	int A, B, C, D;
	cin >> A >> B >> C >> D;

	int numer = A * D + B * C;
	int denom = B * D;

	int gcd = GCD(numer, denom);

	cout << numer / gcd << " " << denom / gcd << "\n";

	return 0;
}

 

실행 결과

* 코드를 제출한 시점과 글 작성 시점이 달라, 주석 추가 등의 이유로 실행 결과의 코드 길이는 상이할 수 있음.