[백준] 20003번 (python 파이썬)

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

 

NTS 코테를 봤다..

1번문제가 유클리드 호제법을 활용한 문제였다고한다..(생각도 못함..)

생각나서 gcd관련문제를 풀어봤다...ㅜ

분모들의 lcm과 분자들의 gcd를 구하는 문제이다. 

 

 

gcd를 구하는 방법은 유클리드 호제법을 이용하여 구할 수 있다.

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

 

이를 통해서 lcm또한 구할 수 있다.

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

 

전체 코드

기약분수는 fractions 함수를 통해서 쉽게 구할 수 있다.

import fractions


n = int(input())

ups = list()
downs = list()

for _ in range(n):
    up, down = map(int, input().split())
    number = fractions.Fraction(up, down)
    ups.append(number.numerator)
    downs.append(number.denominator)

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


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

if n == 1:
    result_gcd = ups[0]
    result_lcm = downs[0]
else:
    result_gcd = gcd(ups[0], ups[1])
    result_lcm = lcm(downs[0], downs[1])

for i in range(2, n):
    result_gcd = gcd(result_gcd, ups[i])
    result_lcm = lcm(result_lcm, downs[i])

print(result_gcd, result_lcm)