[python] 5618. 공약수

문제: https://www.acmicpc.net/problem/5618

 

풀이

이번 문제는 공약수를 구하는 문제입니다.

 

난이도는 브론즈라 어렵지 않았는데, 포스팅까지 하는 이유는 '시간 초과' 때문입니다. 

저도 쉽게 코드를 작성했는데 바로 시간 초과가 나더라구요 ㅠ. ㅠ 

 

문제점이 무엇인지 파악해보도록 합시다 ! 

 

공약수는 숫자 n개가 공통적으로 나눠지는 수를 의미하기 때문에

저는 직관적으로 1부터 작은 수 까지의 범위를 돌고 나눠지는 수를 구하는 방식으로 풀었습니다. 

 

해당 문제는 숫자 두 개 혹은 세 개의 공약수를 찾는 문제였기 때문입니다.

 

문제의 제한 시간은 1초 였는데요.

작은 수가 최대 10의 8제곱(1억) 까지 갈 수 있기 때문에 

1초에 2000만번의 연산을 하는 파이썬으로는 시간 초과가 나는 것입니다. 

 

따라서 O(N)이 아니라 O(루트 N)만큼의 연산을 할 수 있도록 구현해야 합니다.

 

 

그렇다면 아래의 방법처럼 풀도록 하겠습니다.

 

1. 최대 공약수를 구하고 (유클리드 호제법)

2. 최대 공약수의 약수를 출력하기

 

---

유클리드 호제법

유클리드 호제법을 통해 최대 공약수를 구해보겠습니다.

유클리드 호제법은 최대 공약수를 쉽게 구하는 방법을 의미하는데요.

 

방법

1. 큰 수를 작은 수로 나눈다

2. 나누는 수를 나머지로 계속 나눈다

3. 나머지가 0이 나오면, 나누는 수가 최대 공약수 ! 

 

예를 들어, 1512와 1008의 최대공약수를 구해보겠습니다.

1. 1512 % 1008 = 504

2. 1008 % 504 = 0

그러면 504가 최대공약수 !

 

이런 로직을 가지고 있는데요.

---

 

해당 문제는 유클리드 호제법을 통해 최대공약수를 구하고,

약수를 구할 때 n까지 구하는 것이 아니라, n 제곱근 까지 구하는 방법으로 풀어보겠습니다.

 

코드 주석을 보시면 

더 이해가 잘 될거에요 - ! 

---

 

 

- 시간 초과난 코드

n = int(input())
arr = list(map(int, input().split()))

common_divisor = []
for i in range(1, min(arr)+1):
    if n == 2:
        if (arr[0] % i == 0) and (arr[1] % i == 0):
            print(i)
    if n == 3:
        if (arr[0] % i == 0) and (arr[1] % i == 0) and (arr[2] % i == 0):
            print(i)

---

 

- 정답 코드

def get_gcd(a, b): # 최대공약수 찾기
    if a < b: # b가 더 클 떄, a가 더 큰 숫자이도록 바꿔줌
        a, b = b, a

    while b != 0: # 나머지가 0이 나오면, 나누는 수가 최대 공약수 !
        a, b = b, a%b
    return a


n = int(input())
arr = list(map(int, input().split()))

if n == 2:
    gcd = get_gcd(arr[0], arr[1]) # n=2
elif n == 3:
    gcd = get_gcd(get_gcd(arr[0], arr[1]), arr[2]) # n=3

common_divisor = []
for i in range(1, int(gcd**(1/2))+1): # 1 ~ gcd의 제곱근까지 돌면서
    if gcd % i == 0: # 약수 찾기
        common_divisor.append(i)
        if (i**2) != gcd: # 약수의 짝 찾기 -> ex. (1 * 25) = 25
            common_divisor.append(gcd//i)

common_divisor = sorted(common_divisor) # 정렬해주고 출력 ! 
for i in common_divisor:
    print(i)

---