💡문제접근
- 기약분수의 형태를 가지기 위해서 최대공약수를 적절히 활용해서 코드를 작성했다.
💡테스트케이스
입력
2 7
3 5
출력
31 35
+ = + = =
- 이 때, 분모(denominator)와 분자(numerator)의 최대공약수가 1 즉, 서로소 형태라면 그대로 출력하면 된다. 만약 최대공약수가 1이 아닌 다른 수 즉, 서로소 형태가 아니라면 최대공약수로 나눠 기약분수 형태로 만들어서 출력하면 된다.
💡코드(메모리 : 32540KB, 시간 : 36ms)
import math
A, B = map(int, input().split())
C, D = map(int, input().split())
denominator = B * D
numerator = A * D + B * C
if math.gcd(denominator, numerator) == 1:
print(numerator, denominator)
else:
temp = math.gcd(denominator, numerator)
denominator //= temp
numerator //= temp
print(numerator, denominator)📌 유클리드 호제법 알고리즘
-
유클리드 호제법이란, 숫자 a, b가 있을 때,
a를 b로 나눈 나머지와b의 최대공약수는a와 b의 최대공약수가 같다. -
계속해서 a를 b로 나누어서
b의 값을 a에 대입하고a를 b에 나눈 나머지를 b에 대입시켜서 b가 0이 될 때까지 반복을 하면 남게 되는a가 최대공약수가 된다.
def gcd(a, b):
while b > 0:
a, b = b, a % b
return a