[알고리즘]백준 1735: 분수합

알고리즘 유형: 수학 

 

2 초

128 MB

16571

7681

6452

48.225%

문제

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

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

입력

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

출력

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

풀이

---

두 분수를 통분하여 기약분수를 만들어줍니다.

gcm를 이용해 두 분수를 통분하여, 더해줍니다 

이때 분자와 분모 간의 gcm이 1이 아니라면 약분이 가능하므로 이를 나누어주면 됩니다 

import sys
from math import gcd 
 
A,C=map(int,sys.stdin.readline().strip().split())
B,D=map(int,sys.stdin.readline().strip().split())
lcm= (C*D)//gcd(C,D)
new_A, new_B = (lcm//C)*A, (lcm//D)*B
AB = new_A+new_B
lcm2 = gcd(AB, lcm)
print(f"{(new_A+new_B)//lcm2} {lcm//lcm2}")