[백준] 1735 분수 합 - Python

백준 실버3 1735 분수 합 Python

https://www.acmicpc.net/problem/1735

1735번: 분수 합

---

문제

---

코드

맞았습니다가 뜬 코드입니다. - 메모리 31256KB | 시간 40ms | 코드 길이 298B

import sys
arr1 = list(map(int, sys.stdin.readline().rstrip().split()))
arr2 = list(map(int, sys.stdin.readline().rstrip().split()))
a = arr1[0] * arr2[1] + arr1[1] * arr2[0]
b = arr1[1] * arr2[1]
def gcd(a, b):
    while b > 0:
        a, b = b, a % b
    return a
x = gcd(a, b)
print(a//x, b//x)

gcd는 유클리드 호제법을 이용하여 최대공약수를 구하는 함수입니다.

 

유클리드 호제법(유클리드 알고리즘)은 최대공약수를 구하는 알고리즘입니다. 호제법이란 말은 두 수가 서로 상대방 수를 나누어서 결국 원하는 수를 얻는 알고리즘을 나타냅니다.

 

a와 b가 있을 때(a > b), a와 b의 나머지와 b의 최대공약수는 a와 b의 최대공약수와 같습니다.

파이썬으로 유클리드 호제법의 알고리즘을 구현한 것은 다음과 같습니다.

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

 

이를 이용하여 최소공배수를 구할 수도 있습니다.

마찬가지로 a와 b가 있다고 했을 때에,

최소공배수 = 최대공약수 * (a / (최대공약수) * b / (최대공약수)) 이기 때문에 간단하게 계산하면,

최소공배수 = a * b / 최대공약수

이라는 식을 도출 할 수 있습니다.

따라서 파이썬으로 최소공배수를 구하는 코드는 다음과 같습니다.

def lcm(a, b):
    return a * b / gcd(a, b)

 

---

Try 1.

시간초과가 뜬 코드입니다. - 코드 길이 311B

import sys
arr1 = list(map(int, sys.stdin.readline().rstrip().split()))
arr2 = list(map(int, sys.stdin.readline().rstrip().split()))
a = arr1[0] * arr2[1] + arr1[1] * arr2[0]
b = arr1[1] * arr2[1]
for i in range(2, min(a, b)):
    if a % i == 0 and b % i == 0:
        a = a // i
        b = b // i
print(a, b)

• 유클리드 호제법을 이용하지 않았습니다.

---

Search 🔍

• 유클리드 호제법 : https://velog.io/@jwisgenius/%EC%95%8C%EA%B3%A0%EB%A6%AC%EC%A6%98-%ED%8C%8C%EC%9D%B4%EC%8D%AC-%EC%B5%9C%EB%8C%80%EA%B3%B5%EC%95%BD%EC%88%98%EC%9C%A0%ED%81%B4%EB%A6%AC%EB%93%9C-%ED%98%B8%EC%A0%9C%EB%B2%95-%EC%B5%9C%EC%86%8C%EA%B3%B5%EB%B0%B0%EC%88%98

---

오늘의 유우머

공대생의 기침소리는?

 

클록(clock)! 클록(clock)!

 

🤣