문제 이해

수열의 숫자 중 X와 서로소인 수들을 고르고 평균을 구하는 문제이다.

---

문제 풀이

서로소라는 것은 결국 2개의 최대공약수가 1이라는 의미이다.

Python에서는 최대공약수 구하는 함수가 구현되어 있고 JAVA에서는 구현되어 있지 않은데, JAVA에서 구현하려다 에러가 너무 많이 발생해서 그냥 Python을 통해 문제를 풀었다.

---

코드

import math

N = int(input())
lists = list(map(int, input().split(" ")))
X = int(input())
dp = [0]*1000001

sum = 0
count = 0
for d in lists:
    if dp[d]==0:
        if math.gcd(d, X)==1:
        # 서로소인 경우
            dp[d] = 1
            sum+=d
            count+=1
        else:
            dp[d] = 2

    elif dp[d]==1:
        sum+=d
        count+=1

print(sum/count)

---

결과

• 시간 초과가 발생한 것을 보고 최대 공약수를 구하는 알고리즘 시간을 더 줄이려고는 했지만, 쉽지 않아 이미 구현되어 있는 Python 라이브러리를 활용했다.