[백준 3036 파이썬] 링 (실버3, 정수론)

알고리즘 유형 : 정수론
풀이 참고 없이 스스로 풀었나요? : O(풀이 참고 후 일부 최적화)

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

소스 코드(파이썬)

import sys
input = sys.stdin.readline

N = int(input())
ring = list(map(int, input().split()))

# 두 수의 최대공약수를 구하는 함수(유클리드 호제법)
def findGCD(a, b):
    num = b
    div = a
    rest = b % a
    while rest != 0:
        num = div
        div = rest
        rest = num % div
    return div

# i 번째 링 도는 횟수 = 첫 번째 링 반지름 / i 번째 링 반지름
# 2파이r / 2파이r' 형태에서, 2*파이는 약분되므로, 반지름만 고려해준다.
d = ring[0]
for idx in range(1, N):
    d_idx = ring[idx]
    GCD = findGCD(d, d_idx)
    print(f'{d//GCD}/{d_idx//GCD}')

풀이 요약

1. 수학적 지식

   "기약분수를 만드는 법 : 분자와 분모의 최대공약수를 분자, 분모에 각각 나눠준다."

2. i 번째 링은 첫 번째 링의 원주만큼 회전하므로, 회전 바퀴 수는 첫 번째 링의 원주를 i번째 링의 원주로 나눠준 값이다. 이 때, 2*파이는 약분되므로 반지름만 고려하면된다.

3. 유클리드 호제법으로 분자와 분모의 GCD를 구하고 분자 분모에 나눠주자.

배운 점, 어려웠던 점

• 파이와 더불어, 곱하기 2까지 약분된다는 사실을 놓쳤다.

• 기약분수 만드는 법이 "분자와 분모의 최대공약수를 구하고, 분자와 분모에 각각 나눠준다" 라는 것을 알게되었다.