백준 1735번 : 분수 합

문제

분수 A/B는 분자가 A, 분모가 B인 분수를 의미한다. A와 B는 모두 자연수라고 하자. 

두 분수의 합 또한 분수로 표현할 수 있다.

두 분수가 주어졌을 때, 그 합을 기약분수의 형태로 구하는 프로그램을 작성하시오.

기약분수란 더 이상 약분되지 않는 분수를 의미한다.

---

입력

첫째 줄과 둘째 줄에, 각 분수의 분자와 분모를 뜻하는 두 개의 자연수가 순서대로 주어진다.

입력되는 네 자연수는 모두 30,000 이하이다.

출력

첫째 줄에 구하고자 하는 기약분수의 분자와 분모를 뜻하는 두 개의 자연수를 빈 칸을 사이에 두고 순서대로 출력한다.

---

예제 입력 1

2   7

3   5

예제 출력 1

31  35

---

해결 방법

유클리드 호제법 (Euclidean Algorithm)을 이용해서 계산하였다.

두 분수가 주어졌을 때, 그 합을 기약분수의 형태로 구하는 문제이다.

입력 값으로는 A/B 와 C/D가 주어지며, 이 두 값으로 일반적인 분수 합 연산을 해준 다음

유클리드 호제법을 활용해서 만든 gcd 함수에 넣고 최대 공약수를 구한다.

구한 최대 공약수로 나눈 결과값이 원하는 기약분수 형태의 합이 된다.   

PyPy3로 체출하였고 메모리 : 121220 KB   시간 : 100ms

소스 코드

def gcd(A,B):
    mod = A % B
    while mod > 0:
        A = B
        B = mod
        mod = A % B
    return B
        
A, B = map(int,input().split())
C, D = map(int,input().split())
x = A*D + C*B
y = B*D
N = gcd(x,y)

print(x//N, y//N)