[백준] 1735번 : 분수 합 - 파이썬(Python) - 우당탕탕 개발자 되기 프로젝트

 

1735번: 분수 합

 

1. 문제 설명

2. 풀이과정

해당 문제는 두 분수를 입력받아 그 합을 구하는 문제이다.

두 분수를 더했을 때, 그 결과를 기약분수로 구해야 한다.

기약분수는 더 이상 약분되지 않는 분수이므로 각 분자와 분모의 최대공약수를 구해 분자와 분모를 이로 나눠야 한다.

최대공약수는 유클리드 호제법을 활용하여 빠르게 구할 수 있는데, 유클리드 호제법이란 두 수를 서로 나누어 최대공약수를 구하는 방법이다.

유클리드 호제법은 "a % b = r이라고 할 때, a와 b의 최대공약수는 b와 r의 최대공약수와 같고, 이를 다시 b % r = r'이라고 할 때, b와 r의 최대 공약수는 r과 r'의 최대공약수와 같다."를 활용하여 나머지가 0이 되었을 때 나누는 수가 원래 두 수의 최대공약수임을 활용하는 방법이다.

 

1. sys.stdin.readline() 함수를 사용하기 위해 sys 모듈을 불러온다. import sys
2. 첫 번째 분수의 분자와 분모를 입력받는다. A, B = map(int, sys.stdin.readline().split())
3. 두 번째 분수의 분자와 분모를 입력받는다. C, D = map(int, sys.stdin.readline().split())
4. 두 분수의 합의 분자를 계산한다. X = A * D + B * C
5. 두 분수의 합의 분모를 계산한다. Y = B * D
6. 분자와 분모를 기약분수로 만들기 위해 최대공약수를 구하는 함수를 생성한다. def gcd(m, n)
7. 만약 더 작은 수가 0이면 그대로 큰 수를 반환하며 종료한다. if (n == 0): return m
8. 그게 아니면 두 수를 나눈 나머지를 구한다. mod = m % n
9. 만약 나머지가 0이 아니면 나눠지는 수를 나눈 수로, 나누는 수를 나머지로 바꾼다. if (mod != 0): m, n = n, mod
10. 바꿔진 수로 다시 최소 공배수를 찾는다. return gcd(m, n)
11. 반면에 나머지가 0이면 나누는 수인 작은 수를 반환한다. else: return n
12. 분자와 분모를 비교하여 큰 수, 작은 수 순서대로 함수에 대입해 최대공약수를 구한다. MAX = gcd(X, Y) if (X > Y) else gcd(Y, X)
13. 각 분자와 분모를 최대공약수로 나눈다. X //= MAX  Y //= MAX
14. 분자와 분모를 출력한다. print(X, Y)

반응형

3. 소스코드

import sys

A, B = map(int, sys.stdin.readline().split())
C, D = map(int, sys.stdin.readline().split())

X = A * D + B * C
Y = B * D

def gcd(m, n):
    if (n == 0):
        return m
    
    mod = m % n
    if (mod != 0):
        m, n = n, mod
        return gcd(m, n)
    else:
        return n
        
MAX = gcd(X, Y) if (X > Y) else gcd(Y, X)
X //= MAX
Y //= MAX

print(X, Y)