[Python] 백준 21920 - 서로소 평균 문제 풀이

Overview

BOJ 21920번 서로소 평균 Python 문제 풀이
분류: Math (수학)

문제 페이지

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

풀이 코드 1 - 유클리드 호제법

from sys import stdin
from collections import defaultdict


dp = defaultdict(int)


def get_gcd(a: int, b: int) -> int:
    if b == 0:
        return a
    if a < b:
        a, b = b, a
    return get_gcd(b, a % b)


def main():
    def input():
        return stdin.readline().rstrip()

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

    total, cnt = 0, 0
    for num in seq:
        if not dp[num]:
            dp[num] = get_gcd(x, num)
        if dp[num] == 1:
            total += num
            cnt += 1

    print(total / cnt)


if __name__ == "__main__":
    main()

x와 수열의 각 숫자의 최대공약수를 구하여 서로소 여부를 체크한다. 최대공약수는 유클리드 호제법을 이용하여 구한다. 그리고 구한 최대공약수는 dp에 저장하여 동일한 숫자가 나오면 빠르게 구할 수 있게 한다.

풀이 코드 2 - math.gcd

from sys import stdin
from collections import defaultdict
from math import gcd


dp = defaultdict(int)


def main():
    def input():
        return stdin.readline().rstrip()

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

    total, cnt = 0, 0
    for num in seq:
        if not dp[num]:
            dp[num] = gcd(x, num)
        if dp[num] == 1:
            total += num
            cnt += 1

    print(total / cnt)


if __name__ == "__main__":
    main()

math 패키지의 내장 함수를 이용하여 최대공약수를 구하도록 변경하였다. 속도는 이전 코드보다 빠르다.