[백준 / Python] 3036번 링

문제

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

3036번: 링

---

---

해결 코드

def gcd(a, b):
    if a < b:
        a, b = b, a
    # a가 크다
    while True:
        if a % b == 0:
            return b
        else:
            a, b = b, a % b
        
n = int(input())
data = list(map(int, input().split()))
for i in range(1, n):
    tempgcd = gcd(data[0], data[i])
    print('%s/%s' % (data[0]//tempgcd, data[i]//tempgcd))

유클리드 호제법을 사용하여 첫 번째 링과 n 번째 링의 최대공약수를 구하고, 

최대공약수로 각 링을 나누면 된다.