[BOJ] 1735 | 분수 합

문제링크

---

1735 | 분수 합

풀이과정

---

유클리드 호제법을 이용해서 풀면 된다.(유클리드 호제법 정리는 여기 클릭쓰)

분모의 최소공배수를 먼저 구해준 후, 현재 분모에서 최소 공배수로 가기 위해 곱해야 하는 수를 분자에도 곱해준다.

그러면 분자와 분모를 구할 수 있고, 기약분수인지 확인하기 위해 다시 최대공약수를 구해보고, 1이 아니라면 약분을 해주면 된다.

코드

---

frac1 = list(map(int, input().split()))
frac2 = list(map(int, input().split()))

def GCD(a, b):
    while b:
        a, b = b, a % b
    return a
    
def LCM(a, b):
    result = (a * b) // GCD(a, b)
    return result

down = LCM(frac1[1], frac2[1])
up = frac1[0] * (down // frac1[1]) + frac2[0] * (down // frac2[1])

tmp = GCD(up, down)
if tmp != 1:
    up, down = up // tmp, down // tmp

print(up, down)

결과

---