[백준] 3036 링

문제출처] https://www.acmicpc.net/problem/3036

---

문제요약

톱니바퀴가 맞물려 돌아갈 때 회전 수 구하는 문제

풀이

첫 번째 링과 각 링의 최대 공약수를 구하여 각각 나누어 준 후 첫 번째 링을 최대 공약수로 나눈 몫은 분자로 나머지 링을 최대 공약수를 나눈 몫은 분모로 취하면 된다.

최대 공약수를 구하는 방법은 2609번 최대공약수와 최소공배수 문제의 유클리드 호제법을 이용하면된다.
2609번문제풀이 링크]  https://zero-rabbit.tistory.com/53

---

소스코드는 Python 3으로 작성되었습니다.

import sys

input = sys.stdin.readline


def gcd(a, b):
    # 무조건 a > b 유지
    if a > b:
        pass
    else:
        a, b = b, a

    while b > 0:
        r = a % b
        a, b = b, r

    return a


n = int(input())
rings = list(map(int, input().split()))
first = rings[0]

for i, ring in enumerate(rings):
    if i == 0: continue
    g = gcd(first, ring)
    print(first // g, '/', ring // g, sep='')