[BOJ] 링 - 3036 (S4)

시간 제한	메모리 제한
1 초	128 MB

문제

상근이는 창고에서 링 N개를 발견했다. 상근이는 각각의 링이 앞에 있는 링과 뒤에 있는 링과 접하도록 바닥에 내려놓았다.

상근이는 첫 번째 링을 돌리기 시작했고, 나머지 링도 같이 돌아간다는 사실을 발견했다. 나머지 링은 첫 번째 링 보다 빠르게 돌아가기도 했고, 느리게 돌아가기도 했다. 이렇게 링을 돌리다 보니 첫 번째 링을 한 바퀴 돌리면, 나머지 링은 몇 바퀴 도는지 궁금해졌다.

링의 반지름이 주어진다. 이때, 첫 번째 링을 한 바퀴 돌리면, 나머지 링은 몇 바퀴 돌아가는지 구하는 프로그램을 작성하시오.

입력

첫째 줄에 링의 개수 N이 주어진다. (3 ≤ N ≤ 100)

다음 줄에는 링의 반지름이 상근이가 바닥에 놓은 순서대로 주어진다. 반지름은 1과 1000를 포함하는 사이의 자연수이다.

출력

출력은 총 N-1줄을 해야 한다. 첫 번째 링을 제외한 각각의 링에 대해서, 첫 번째 링을 한 바퀴 돌리면 그 링은 몇 바퀴 도는지 기약 분수 형태 A/B로 출력한다.

풀이

크게 3가지 경우가 존재하며 그에 대한 출력은 다음과 같다.

1. 첫 번째 링의 크기를 링 하나의 크기로 나누었을 때 나누어 떨어지는 경우.

   print(f"{first // r}/1")

   첫 번째 링의 크기가 더 크며 배수 - 약수의 관계이므로 첫 번째 링을 현재 확인하고 있는 링의 크기로 나눈 몫을 분자로, 1을 분모로 하여 출력한다.

2. 링 하나의 크기를 첫 번째 링의 크기로 나누었을 때 나누어 떨어지는 경우.

   print(f"1/{r // first}")

   현재 링의 크기가 더 크며 배수 - 약수의 관계이므로 현재 링의 크기를 첫 번째 링의 크기로 나눈 몫을 분모로, 1을 분자로 하여 출력한다.

3. 둘 다 나누어 떨어지지 않는 경우

   이 경우 한 쪽의 값으로 나누어 떨어지지 않기 때문에 분자와 분모를 약분해야 한다. 약분은 각 수를 최대공약수로 나누면 구할 수 있다.

   최대 공약수는 유클리드 호제법으로 구할 수 있다.

코드

n = int(input())
ring = list(map(int, input().split()))
first = ring[0]
rings = ring[1:]
def gcd(a, b):
    while a % b != 0:
        r = a % b
        a, b = b, r
    return b

for r in rings:
    if first % r == 0:
        print(f"{first // r}/1")
    elif r % first == 0:
        print(f"1/{r // first}")
    else:
        g = gcd(first, r)
        print(f"{first // g}/{r // g}")