백준 3036번 링 파이썬

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

3036번: 링

 

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

이 문제의 핵심은 최대공약수를 구하여 각 수들을 나눠주는 것 이라고 생각 한다.

 

---

 

만약 math 라이브러리를 모르고 gcd() 함수를 모른다면, 아래와 같이 직접 gcd 알고리즘을 짜는것도 좋은 방법이다.

아래 코드도 정답이다.

N = int(input())
r = list(map(int, input().split()))
fix = r[0]
for i in range(1, N):
    Min = min(r[i] , fix)
    for j in range(Min, 0, -1): #gcd
        if (fix % j) == 0 and (r[i] % j) == 0:
            gcd = j
            break
    print(f'{fix//gcd}/{r[i]//gcd}')