[python] 백준 3036 : 링

[python] 백준 3036 : 링

3036번: 링 (acmicpc.net)

3036번: 링

실버 3

수학, 정수론, 유클리드 호제법

---

접근

기약분수는 분모와 분자를 더이상 약분할 수 없는 분수를 뜻한다.

따라서 분모와 분자의 최대공약수로 나누는 방법으로 구할 수 있다.

 

12와 3의 경우 최대공약수가 3이므로 각각을 3으로 나누면

4와 1이 된다. 이를 분자/분모의 형태로 출력하도록 만들어야 한다.

 

코드 (최대공약수를 반환하는 라이브러리 사용)

import sys; input = sys.stdin.readline
from math import gcd
N = int(input())
lst = list(map(int, input().split()))
for i in range(1, N):
    num_gcd = gcd(lst[0], lst[i])
    print(f'{lst[0]//num_gcd}/{lst[i]//num_gcd}')

 

코드 (유클리드 호제법으로 최대공약수를 구함)

import sys; input = sys.stdin.readline
def gcd(x, y):
    while y:
        x, y = y, x%y
    return x

N = int(input())
lst = list(map(int, input().split()))
for i in range(1, N):
    num_gcd = gcd(lst[0], lst[i])
    print(f'{lst[0]//num_gcd}/{lst[i]//num_gcd}')

 

[파이썬] 유클리드 호제법을 이용한 최대공약수, 최소공배수 구하기 (tistory.com)

[파이썬] 유클리드 호제법을 이용한 최대공약수, 최소공배수 구하기