백준 문제 풀이 - 공약수 5618번

📜 문제 이해하기

자연수 n개가 주어진다. 이 자연수의 공약수를 모두 구하는 프로그램을 작성하시오.

💡 문제 재정의

n개의 공약수를 모두 구해 출력하면 되는 문제

✏️ 계획 수립

1. n개의 숫자들의 최대 공약수를 구한다.
2. 최대 공약수는 유클리드 알고리즘으로 구하되 gcd(a,b,c) = gcd(a, gcd(b, c))라는 사실을 이용한다.
3. 최대 공약수의 약수를 출력한다.

💻 계획 수행

import sys


def get_gcd(a, b):
    while b > 0:
        a, b = b, a % b
    return a


if __name__ == '__main__':
    n = int(sys.stdin.readline())

    num_list = list(map(int, sys.stdin.readline().rstrip().split()))
    while len(num_list) > 1:
        num_list.append(get_gcd(num_list.pop(), num_list.pop()))

    gcd = num_list.pop()
    for i in range(1, gcd // 2 + 1):
        if gcd % i == 0:
            print(i)
    print(gcd)

특이사항은 마지막 약수를 구할때 gcd의 반까지만 반복한다. gcd의 자기자신이 아닌 가장 큰 약수는 아무리 커도 gcd // 2 + 1보다 작기때문이다. 왜냐하면 1이 아닌 짝을 이루는 약수의 최소는 2이기 때문이다. 약수의 성질은 곰곰히 생각하면 반복문을 반으로 줄일 수 있다.

🤔 회고

이 문제는 유클리드 호제법과 약수의 성질을 활용해 문제를 풀었다. 문제 자체의 난이도는 어렵진않지만 시간이 생각보다 빡빡하기 때문에 pypy3으로 제출했을때만 풀렸다.