[백준 1735] 분수 합

문제 링크 : https://www.acmicpc.net/problem/1735

1735번: 분수 합

 

필요 알고리즘 :

 

유클리드 호제법

 

 

자연수 A와 B에 대해 A/B라는 분수가 있을 때

 

이를 기약분수로 형태로 변환하는 문제이다.

 

두개의 입력되는 분수에 대하여 A와 B를 구하는 방법은 쉽다.

 

그러나 A/B꼴의 분수를 기약분수로 변환하는 과정에서 문제가 생긴다.

 

---

 

기약분수로 변환하기 위해서는 먼저 A와 B의 최대공약수를 구해야된다.

 

기존의 방법으로 최대공약수를 구하기 위해서는 min(A, B) 횟수 만큼의 연산이 수행되어야 한다.

 

 

입력되는 두 분수의 분모가 모두 30000일 경우

 

더한 분수의 분모는 9억이 되고 이는 최대공약수를 구하는데 9초의 시간이 소요된다.

 

이는 곧 시간초과 이므로 이 문제는 유클리드 호제법을 이용해 구해야한다.

 

---

 

위 사실만 안다면 구현은 어렵지 않다.

 

#include <stdio.h>

int gcd(int a, int b) {
	if (a % b == 0)return b;
	return gcd(b, a % b);
}

int main(void) {
	int a, b, c, d;
	int e, f;
	scanf("%d %d", &a, &b);
	scanf("%d %d", &c, &d);

	e = a * d + c * b;
	f = d * b;
	int div = gcd(e, f);
	e /= div;
	f /= div;
	printf("%d %d", e, f);
}