swea 13549번 파이썬 문제풀이(최대공약수의 최대화)

https://swexpertacademy.com/main/code/problem/problemDetail.do?contestProbId=AX6PUEfaqAADFAS9 

SW Expert Academy

 

---

이 문제 상당히 어려워서 고민을 많이했다. 하루 정도 고민한 뒤에 힌트를 얻어서 풀었다. 자꾸 소인수 분해를 해서 해결할려고하였는데 약수를 구해서 해결할 수 있었다.

문제풀이 방식은 다음과 같다.

1. 문제에서 답은 입력받은 수를 오름차순 했을때 첫번째 아니면 두번째 수의 약수 중에 존재한다.(값을 교체해도 하나만 교체할 수 있기 때문에) + (최대 공약수는 가장 작은수의 크기를 넘을 수 없다.)

 

2. 그렇게 찾은 2개의 약수를 한 리스트안에 넣고 돌면서 입력받은 각각의 수들과 비교해서 해당 수가 공약수가 아닌 횟수가 1번 이하라면 해당 수는 최대 공약수가 될 수 있다.(1번이면 해당 수를 교체해버리면 된다.)

 

3. 2번 중 가장 큰값이 답이다.

 

import math

T = int(input())


# 수 x의 약수를 찾는 함수
def prime_find(x):
    for i in range(1, int(math.sqrt(x)) + 1):

        if x % i == 0:
            prime.append(i)
            if i * i != x:
                prime.append(x // i)


# 첫번째와 두번째 약수 중에서 전체 수와의 공약수를 계산
# 만약 전체를 돈 후에 어떤 수와의 공약수가 아닌것의 개수가 1이하라면
# 해당 공약수는 전체 최대 공약수가 될 수 있다.
def check(x):
    count = 0
    for i in range(n):
        if arr[i] % x != 0:
            count += 1
    return count <= 1


for order in range(1, T + 1):
    n = int(input())
    arr = list(map(int, input().split()))

    arr.sort()
    prime = []  # 약수를 담을 함수
    # 문제에서 아무리 많아야 수를 1개 제거(교체)할 수 있기 때문에
    # 오름차순 정렬했을 때 반드시 첫번째와 두번째 값중 하나의 약수중에서 최대공약수가 나온다.
    prime_find(arr[0])
    prime_find(arr[1])
    result = 0  # 최대공약수를 출력할 변수
    # 저장된 약수 중에서 전체 수와 비교하여 최대 공약수를 찾는다.
    for i in prime:
        if check(i):
            result = max(result, i)
    print(f'#{order} {result}')