[백준] 21920 서로소 평균

📖 문제

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

💻 내 코드

import sys
import math

n=int(sys.stdin.readline())
nums=list(map(int, sys.stdin.readline().split()))
x=int(sys.stdin.readline())

mlist=[]

for num in nums:
    if math.gcd(num, x)==1:
        mlist.append(num)
print(sum(mlist)/len(mlist))

💡 풀이

• 처음에는 모든 수의 약수를 모두 구한 뒤 그 약수가 x의 약수에도 있는지 확인하는 방법을 써서 시간초과가 나왔다

처음 제출한 코드

n=int(input())
nums=list(map(int, input().split()))
x=int(input())

mlist=[]
for i in range(2, x+1):
    if x%i==0:
        mlist.append(i)

alist=[]
for i in nums:
    cnt=0
    for j in range(2, i+1):
        if i%j==0:
            if j in mlist:
                cnt+=1
        if cnt==0:
            alist.append(i)
print(sum(alist)//len(alist))

• 하지만 이럴 필요 없이 x와 입력된 수의 최대공약수를 구한 뒤 그 수가 1이라면 서로소임을 알 수 있다
• 최대공약수를 구하기 위해 최대공약수를 구하는 함수를 생성하지 않고 math의 gcd 함수를 이용했다