[백준] 14490번 > 백대열

www.acmicpc.net/problem/14490

14490번: 백대열

문제

대열이는 욱제의 친구다.

• “야 백대열을 약분하면 뭔지 알아?”
• “??”
• “십대일이야~ 하하!”

n:m이 주어진다. 욱제를 도와주자. (...)

입력

n과 m이 :을 사이에 두고 주어진다. (1 <= n, m <= 100,000,000)

출력

두 수를 최대한으로 약분하여 출력한다.

예제 입력 1

100:10

예제 출력 1

10:1

예제 입력 2

18:24

예제 출력 2

3:4

 

---

풀이

외장함수 gcd(최소공약수)를 활용하였다.

from math import gcd
n, m = map(int, input().split(':'))
while True:
    gcd_num = gcd(n, m)
    if gcd_num == 1:
        break
    n //= gcd_num
    m //= gcd_num
print(str(n) + ":" + str(m))