[구현/수학] 백준 1735 분수 합 - Python

 

[ Contents ]

 

 

1. 문제 (링크 참조)

1735번: 분수 합

 

 

 

2. 문제 풀이

 두 분수의 합을 구하는 문제입니다. 다만, 그 합은 기약분수여야 합니다.

 

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

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

 두 분수를 통분해서 합을 구합니다. 그 후, 분자 분모의 최대공약수를 구해 약분합니다. 최대공약수는 유클리드 호제법을 이용하면 쉽게 구할 수 있습니다.

 

 

 

3. 코드

a, b = map(int, input().split())
c, d = map(int, input().split())

numerator = a*d + b*c #분자
denominator = b*d #분모

 두 분수를 통분해서 더해줍니다.

 a/b와 c/d의 합은 (a*d + b*c) / b*d 입니다.

 

 

# 유클리드 호제법을 통한 최대공약수
x = numerator
y = denominator
while x != y:
    if x > y:
        x -= y
    else:
        y -= x
print(numerator//x, denominator//x)

 유클리드 호제법을 이용해서 최대공약수를 구합니다. 빼는 방법을 이용해도, 시간초과없이 통과합니다. 해당 코드의 설명은 [ 2. 문제 풀이의 링크 ]에서 보실 수 있습니다.