2981 검문

문제 해결을 위한 수학적 알고리즘 2개

1. 유클리드 호제법으로 최대 공약수를 구한다.

2. 약수들을 효율적으로 찾아야 한다. -> 시간초과의 주 원인

 

우선 입력된 숫자들을 정렬하고, 가장 작은 값을 뺐다.

그러면 최대 공약수를 구할 수 있는 숫자들의 모습이 보인다.

 

 

유클리드 호제법을 사용하여 최대 공약수를 구한다.

# 최대공약수 구하는 함수
def get_gcd(a, b):
    if b == 0:
        return a
    c = a % b
    return get_gcd(b, c)

이제 최대 공약수의 약수들을 구해야하는데, 1부터 for문으로 세었다가 시간초과를 맞았다.

숫자가 9999990 999999891 이런식이면 엄청 오래걸린다.

그렇다고 숫자들의 가장 작은 수부터 구하는 것도 이상하고.. 그래서 결국 검색했다.

 

약수들을 효율적으로 찾는 방법은 이미 찾은 약수의 짝을 방문해서 구하지 않는 것이다.

https://inuplace.tistory.com/459

[알고리즘 연습] 약수 구하기 효율화 (by Python)

# get answers - 최대 공약수의 약수들 저장하기
def get_divisor(n):
    divisors = []
    divisors_back = []

    for i in range(1, int(n ** (1/2)) + 1):
        if n % i == 0:
            if i != 1:
                divisors.append(i)
            if i != n // i:
                divisors_back.append(n // i)

    return divisors + divisors_back[::-1]

 

---

제출 코드

import sys

N = int(sys.stdin.readline().rstrip())
numbers = []
# 입력 받고
for _ in range(N):
    numbers.append(int(sys.stdin.readline().rstrip()))

numbers.sort()
min_num = numbers[0]
# 모든 수에서 가장 작은 수 만큼을 뺀다.
for i in range(N):
    numbers[i] -= min_num


# 최대공약수 구하는 함수
def get_gcd(a, b):
    if b == 0:
        return a
    c = a % b
    return get_gcd(b, c)


gcd = 0
for i in range(N-1):
    gcd = get_gcd(gcd, numbers[i + 1])


# get answers - 최대 공약수의 약수들 저장하기
def get_divisor(n):
    divisors = []
    divisors_back = []

    for i in range(1, int(n ** (1/2)) + 1):
        if n % i == 0:
            if i != 1:
                divisors.append(i)
            if i != n // i:
                divisors_back.append(n // i)

    return divisors + divisors_back[::-1]


answers = get_divisor(gcd)
print(' '.join(map(str, answers)))