[백준] Python - 21920 서로소 평균

문제 링크

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

21920번: 서로소 평균

 

문제 풀이

처음에는 각 수마다 약수를 구해서 서로소(1 이외의 공약수가 없음)인지 비교하여 풀이하려고 했다. 하지만 계속해서 시간초과 ㅠㅠ 결국 파이썬의 math.gcd()를 사용하여 코드를 완성했다... 아래 더보기는 직접 약수를 구해주는 함수를 구현하여 이용한 코드(다른 블로그 도움..)인데, 시간이 더 많이 소요된다. 다음엔 유클리드 호제법을 이용한 최대공약수로도 풀이해봐야겠다! 

 

 

약수를 구해주는 함수를 구현하여 이용한 코드

n = int(input())
a = list(map(int, input().split()))
x = int(input())
result = 0
cnt = 0

def getDivisor(num) :
    divisorList = []
    for i in range(1, int(num**0.5)+1) :
        if num % i == 0 :
            divisorList.extend([i, num//i])
    divisorList.remove(1)
    return list(set(divisorList))

xList = getDivisor(x)

for num in a :
    for x in xList :
        if num % x == 0 :
            break
    else :
        result += num
        cnt += 1

print(result / cnt)

 

전체 코드

import math

n = int(input())
a = list(map(int, input().split()))
x = int(input())
result = 0
cnt = 0

for num in a :
    if math.gcd(num, x) == 1 :
        result += num
        cnt += 1

print(result / cnt)