백준 3036번 링 파이썬 풀이

Python

[Python] 백준 알고리즘 온라인 저지 3036 링

 

3036 링

출처

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

3036번: 링

링이 얼마나 회전하는지 예제 출력을 통해 확인할 수 있듯이 최대공약수로 분모와 분자를 나눠주면 회전수를 알 수 있다.

두 가지 방법을 사용하여 소스코드를 작성하려고 한다.

소스코드 1: math.gcd를 import 해서 최대공약수를 구하여 출력

소스코드 2: 유클리드 호제법을 코드로 작성해 최대공약수를 구하여 출력

 

알고리즘 분류

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

---

소스코드 1

from math import gcd
import sys
input = sys.stdin.readline

n = int(input())
rings = list(map(int, input().split()))

for i in range(1, n):
    t = gcd(rings[0], rings[i])
    print(f'{rings[0] // t}/{rings[i] // t}')

 

소스코드 2

import sys
input = sys.stdin.readline

def gcd(a, b):
    if b == 0:
        return a
    return gcd(b, a%b)

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

---

풀이

소스코드 1

최대공약수를 구하는 라이브러리를 가져와서 출력하는 방법이다.

단순히 gcd( A, B )를 통해 A, B의 최대공약수를 계산하여 준다. 이 최대공약수로 첫 번째 링과 i번째 링을 나눠 출력하면 된다.

 

소스코드 2

유클리드 호제법을 이용한 최대공약수를 구하는 방식으로 loop을 돌며 b가 0이 될 때까지 계산하여 최대공약수를 구한다.

---

풀이 결과

소스코드 1

소스코드 2