[Python] 백준 #1735. 분수 합

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

1735번: 분수 합

 

# 1735 - Python 3

import sys

input = sys.stdin.readline

def gcd(a, b):
    while b > 0:
        a, b = b, a % b             # 유클리드 호제법
    
    return a

x, a = map(int, input().split())
y, b = map(int, input().split())

lower = a * b                       # 약분 전 분모
upper = x * b + y * a               # 약분 전 분자

gcd = gcd(lower, upper)
print(upper // gcd, lower // gcd)

< line 5 ~ 9 >

- 유클리드 호제법의 사용

: 숫자 a, b에서 a, b의 최대공약수는 a % b와 b의 최대공약수와 같다.

: 위의 반복문에서 b가 0이 될 때 까지, 유클리드 호제법을 진행하여 최대공약수 찾음

: 최대공약수 gcd 외의 약수를 찾을 필요가 없으므로 시간 줄임