[알고리즘 문제] fractionsum (Python / 파이썬)

문제

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

입력

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

출력

첫째 줄에 구하고자 하는 기약분수의 분자와 분모를 뜻하는 두 개의 자연수를 공백으로 구분하여 순서대로 출력한다.

---

문제 풀이

두 분수가 주어졌을 때, 그 합을 기약분수의 형태로 구하는 문제이다. 

 

먼저, 두 분수의 분자와 분모가 주어졌을 때 

두 분수의 합을 구해준다. 

 

그런 다음, 구한 합의 분자와 분모의 최대 공약수를 구해준 뒤 

각각을 최대 공약수로 나눠주면 기약 분수를 구할 수 있다. 

---

My Code

# 최대 공약수 구하는 함수
def get_gcd(a, b):
    while b > 0:
        a, b = b, a % b
    return a

a, b = map(int, input().split()) # 첫 번째 분수의 분자, 분모
c, d = map(int, input().split()) # 두 번째 분수의 분자, 분모

up = (a * d) + (b * c) # 두 분수 합의 분자
down = b * d           # 두 분수 합의 분모

gcd = get_gcd(up, down) # 두 분수 합 분자, 분모의 최대 공약수

up = up // gcd # 분자를 최대 공약수로 나눠줌
down = down // gcd # 분모를 최대 공약수로 나눠줌

print(up, down)