[백준] 1735번 분수 합

💡문제접근

• 기약분수의 형태를 가지기 위해서 최대공약수를 적절히 활용해서 코드를 작성했다.

💡테스트케이스

입력

2 7
3 5

출력

31 35

$\frac{2}{7}$ + $\frac{3}{5}$ = $\frac{2×5}{7×5}$ + $\frac{3×7}{7×5}$ = $\frac{10+21}{35}$ = $\frac{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

💡소요시간 : 2m