[알고리즘][Python] 백준(BOJ) 1735 분수 합_파이썬

 

1735 분수 합    www.acmicpc.net/problem/1735

1735번: 분수 합

 

 

 

 

 

문제 풀기 전 공부할 것 : 수학, 정수론, 유클리드 호제법

 

 

 

 

 

 

 

풀이 1

<내용>

• 분모들의 최소공배수로 통분하여 계산한다.
• 최대공약수를 구하는 gcd 함수를 만든다.
• 분모들의 최소공배수로 통분하여 분모를 구하고 분자도 구한다.
• 분자와 분모를 기약 분수로 만들기 위해 최대공약수로 나눈다.

 

 

<코드>

def gcd(a, b):
    while a % b != 0:
        mod = a % b
        a = b
        b = mod
    return b

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

g1 = gcd(b, d)
demon = b * d // g1
mole = a * (d//g1) + c * (b//g1)

g2 = gcd(demon, mole)
print(mole//g2, demon//g2)

 

 

 

 

 

 

 

 

 

풀이 2

<내용>

• 위의 풀이에서 최소공배수로 통분하지 않고 두 분모들의 곱을 분모로 구하고 분자도 구한 후 최대공약수로 나누면 된다.

 

<코드>

def gcd(a, b):
    while a % b != 0:
        mod = a % b
        a = b
        b = mod
    return b

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

g = gcd(a*d+b*c, b*d)
print((a*d+b*c)//g, (b*d)//g)