[알고리즘][Python] 백준(BOJ) 14490 백대열_파이썬

 

14490 백대열    https://www.acmicpc.net/problem/14490

14490번: 백대열

 

 

 

 

 

 

문제 풀기 전 공부할 것 : 수학, 문자열, 정수론, 유클리드 호제법

 

 

 

 

 

 

 

풀이

<내용>

• 최대한 약분해야 하기 때문에 최대공약수로 약분하면 된다.
• 최대공약수를 만들어주는 gcd 함수를 만든다.
• 입력이 숫자:숫자이므로 split() 안에 ':'를 넣어 :를 기준으로 분리한다.
• 두 숫자의 최대공약수로 나눈 값을 형식에 맞춰 출력한다.

 

 

<코드>

def gcd(n, m):
    while n % m != 0:
        mod = m
        m = n % m
        n = mod
    return m            

n, m = map(int, input().split(':'))
g = gcd(n, m)
print('%d:%d' %(n//g, m//g))