[백준/Python] 1735번 : 분수 합

시간 제한	메모리 제한	문제 티어	정답 비율
2 초	128 MB	실버 III	48.023%

📜 문제

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

두 분수의 합 또한 분수로 표현할 수 있다. 두 분수가 주어졌을 때, 그 합을 기약분수의 형태로 구하는 프로그램을 작성하시오. 기약분수란 더 이상 약분되지 않는 분수를 의미한다.

 

📥입력

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

 

📤출력

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

 

💡풀이

 분수 A/B와 C/D가 주어졌을 때 분수 합은 (A * D) + (B * C) / (B * D) 인건 다들 알고 있을 것이다.

문제는 여기서 분수 합을 기약분수 합을 나타내는 것인데 기약분수로 나타내기 위해서는 (A * D) + (B * C)와 (B * D) 의 최대공약수 fraction_gcd를 구해주면 된다.

 

최대공약수 구하는 공식은 시간복잡도가 O(n)인 반복문으로 일일이 나누어 구하는 방식 보다 유클리드 호제법(시간복잡도 : O(log n)을 이용하면 빠르고 효율적으로 구할 수 있다.

 

이것을 토대로 최대공약수 fraction_gcd를 구한 뒤 (A * D) + (B * C) / fraction_gcd 와 (B * D) / fraction_gcd 를 출력해주면 된다.

 

아래는 내가 작성한 정답코드이다.

import sys

input = sys.stdin.readline

def gcd(n, d):
  while n * d != 0:
    if n > d:
      n %= d
    else:
      d %= n
  return n + d

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

numerator = (a * d) + (b * c)
denominator = b * d

fraction_gcd = gcd(numerator, denominator)

print(numerator // fraction_gcd, denominator // fraction_gcd)