[Python] 분수 합 - 백준

해당 글은 백준 1735번 문제 '분수 합'을 다룬다.

문제

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

1735번: 분수 합

 

설명

해당 문제는 최종 분수가 기약분수 형태로 되어야 하므로

최대공약수를 구하는 유클리드 호제법을 이용해서 푸는 문제이다.

gcd를 구해서 최종값 분수, 분자 각각에 나누어 주면 된다.

 

https://seunghyum.github.io/algorithm/Euclidean-algorithm/#

[Algorithm] 유클리드 호제법(최대공약수 구하기) 공부

 

코드

# 최대공약수
def gcd(x, y):
    mod = x % y
    while mod > 0:
        x = y
        y = mod
        mod = x % y
    return y

a1, b1 = map(int, input().split())
a2, b2 = map(int, input().split())

A = a1*b2 + a2*b1
B = b1*b2

g = gcd(A, B)
print(A//g, B//g)