Post

19. Python(분수 합)

Posted
By younghoonko
1 min read
19. Python(분수 합)

[toc]

최소공배수

문제

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

제출

코드

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20

import sys

input = sys.stdin.readline

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

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

x = (a * d) + (c * b)
y = b * d

g = gcd(x, y)
x //= g
y //= g

print(x, y)

1
2
3

# 입력
2 7
3 5

1
2

# 출력
31 35

인사이트

  • 기약분수로 나타내기 위해서 분모와 분자의 최대공약수를 구한 후 각각 나누면 된다고 생각했음

풀이

1. 최대공약수(gcd)

1
2
3
4

def gcd(a, b):
    while b > 0:
        a, b = b, a % b
    return a
  • 물론 from math import gcd를 사용해서 할 수 있지만 함수를 구현했음
  • 함수의 로직
    • b가 0이 될 때 a값이 최대공약수가 되는 것

2. 최소공배수(lcm)

  • 최대공약수와 최소공배수의 관계
1
2
3
4
5
6

a = 3(1, 3)
b = 4(1, 2, 4)
gcd = 1

lcm = (a * b) // gcd
lcm = 12 // 1 = 12
  • 관계를 활용하여 분수의 합을 구한 후 분모와 분자의 최대공약수를 구한 후 각각 나눠줌으로써 기약분수의 형태로 변환함
Python, Practice_Python
python python_p