[Python] BOJ 20003 - 거스름돈이 싫어요

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

20003번: 거스름돈이 싫어요

# fractions함수를 배우게 된 문제이다.

# fractions.Fraction(a, b)함수는 a, b가 들어왔을 때 기약분수로 나타내준다.

   ex) fractions.Fraction(4, 10)은 2/5를 출력한다. '2/5' 이런 str형태로 출력되긴하는데 실제 str type은

        아니라서 분자를 출력할땐 tmp = fractions.Fraction(a, b)라 하면

        tmp.numerator로 뽑아내야하고 분모는 tmp.denominator로 뽑아내야 한다.

 

# 처음에 그냥 분모의  '1 / 최소공배수'을 출력하면 되는줄 알고 제출했다가 틀렸다.

    문제를 잘 읽어보니 "새로운 가격 단위는 최대 몇 코인인지를 구해라" 에서 최대를 신경을 쓰지 않았다.

    2/3, 4/5가 있을때 1/15원도 되긴하지만, 최대로 2/15원이 정답이다.

    따라서  '분자의 최대공약수 / 분모의 최소공배수'를 출력하면 된다.

 

import fractions, sys
def gcd(a, b):
    while b > 0:
        a, b = b, a % b
    return a
    
def lcm(a, b):
    return a * b // gcd(a, b)
 
N = int(input())
a, b = map(int,input().split())
tmp = fractions.Fraction(a, b)
if N == 1:
    print(tmp.numerator, tmp.denominator)
    sys.exit(0)
g, l = tmp.numerator, tmp.denominator
for _ in range(N-1):
    a, b = map(int,input().split())
    tmp = fractions.Fraction(a, b)
    g = gcd(g, tmp.numerator)
    l = lcm(l, tmp.denominator)
 
print(g, l)

(solved.ac 티어: 실버 1)