[구현/수학] 백준 14490 백대열 - 파이썬(Python)

 

[ Contents ]

 

 

1. 문제 (링크 참조)

14490번: 백대열

 

 

 

2. 문제 풀이

 두 수의 최대공약수로 나누어서, 최소의 자연수로 비를 표현하는 문제입니다.

 

2022.02.05 - [Algorithm] - [Algorithm] 최대공약수(GCD) 구하기: 유클리드 호제법

[Algorithm] 최대공약수(GCD) 구하기: 유클리드 호제법

 최대공약수는 유클리드 호제법을 통해서 구할 수 있습니다. 단순히 1씩 올리면서 약수를 구하면 시간초과가 납니다.

 

 

 

3. 코드

n, m = map(int, input().split(':'))

#유클리드 호제법
def gcd(x, y):
    if x < y:
        x, y = y, x
    while y != 0:
        x %= y
        x, y = y, x
    return x

gcd = gcd(n, m)
print(f"{n//gcd}:{m//gcd}")