110. 3036 링

import sys
input = sys.stdin.readline

input()

num = list(map(int, input().split()))
result = ""


def GCD(x, y):
    while(y != 0):
        r = x % y
        x = y
        y = r
    return x


numFirst = num[0]

for i in range(1, len(num)):
    if(numFirst % num[i] == 0):
        result += str(int(numFirst / num[i])) + "/1\n"
    else:
        numGCD = GCD(numFirst, num[i])
        result += str(int(numFirst / numGCD)) + "/" + \
            str(int(num[i] / numGCD)) + "\n"


print(result)

문제요약

링 세개가 있는데 첫번째 링을 한 바퀴 돌리면 나머지 링은 몇 바퀴 도는가?

설명

문제는 크게 어렵지 않다.

for i in range(1, len(num)):
    if(numFirst % num[i] == 0):
        result += str(int(numFirst / num[i])) + "/1\n"

만약 회전한 바퀴가 정수로 떨어진다면 위와같이 작성할 수 있다.

ex)

8 4  |  첫 번째가 한 바퀴 돌 때 두번째 링은 두 바퀴를 논다 => 2 / 1

else:
        numGCD = GCD(numFirst, num[i])
        result += str(int(numFirst / numGCD)) + "/" + str(int(num[i] / numGCD)) + "\n"

만약 정수로 떨어지지 않을 경우가 있다.

그 경우에는 두 수의 최대공약수를 구하고 그 공약수로 두 수를 각각 나누어주면 된다.

최대공약수는 유클리드 호제법을 사용하였다.(파이썬은 최대공약수, 최소공배수의 함수를 제공하긴 한다.)

https://smhope.tistory.com/292

유클리드 호제법(최대공약수 구하기)

ex)

12 8  |  정수로 떨어지지 않음, 첫 번째가 한바퀴 돌때, 두 번째는 1.5바퀴 돈다. => 3 / 2 출력 필요

12와 8의 최대공약수는 4이다.

4를 각각 12와 8에 나누어 준다면 3 2가 나온다.