[백준] 14252 - 공약수열 (Python)

문제

서로 다른 양의 정수로 이루어진 크기가 N인 집합 A가 주어진다. 영선이는 집합에 새로운 양의 정수를 추가하려고 한다. 이때, 집합에 있는 수를 정렬한 결과에서 인접한 두 수의 공약수가 1을 넘으면 안 된다. 그러기 위해서 수를 최소 몇 개 추가해야하는지 구하는 프로그램을 작성하시오.

---

입력

첫째 줄에 N이 주어진다. (1 ≤ N ≤ 50)

둘째 줄에는 집합에 포함되어 있는 수가 주어진다. 주어지는 수는 100,000보다 작거나 같은 자연수이다.

출력

첫째 줄에 수를 최소 몇 개 추가해야하는지 출력한다.

---

예제 입력

4
2200 42 2184 17

예제 출력

3

힌트

예제 1의 경우에 {43, 2195, 2199}를 추가하면 된다.

---

해결 방법

정렬된 배열의 연속된 두 수들을 순회하면서 그 사이에 추가해야할 숫자가 있다면 추가해야 할 갯수를 구한다. 

CASE 1. 두 수가 서로소

        두 수가 이미 서로소이기 때문에 아무것도 하지 않음

CASE 2. 두 수가 서로소가 아님

        두 수와 모두 서로소인 숫자가 있다면 그 숫자 하나를 추가 (cnt += 1)

        발견하지 못한다면 숫자 두 개를 추가 (cnt += 2)

추가하는 숫자가 최대 2개인 이유?
* 전제 : 두 정수 a, b사이에는 최소 하나의 서로소인 정수가 항상 존재

* 문제상황 a, b사이에 어떠한 단일 정수도 두 수와 동시에 서로소가 아님
-> a와 서로소인 x
-> b와 서로소인 y
두 수를 추가하여 문제를 해결할 수 있다. 

* 2개의 수로 충분한 이유
- x : a와 서로소이지만, b의 인수를 포함
- y : b와 서로소이지만, a의 인수를 포함
-> a-x-y-b는 인접한 수와 서로소임.

import sys
input = sys.stdin.readline

n = int(input())

nums = list(map(int,input().split()))
nums.sort()

# 최대공약수를 구하는 알고리즘
def _gcd(a,b):
    while a%b != 0:
        tmp = a%b
        a = b
        b = tmp
    return b

cnt = 0
# 인접한 두 수들을 탐색하며
for i in range(0,n-1):
	# 두 수가 서로소인지 체크
    if _gcd(nums[i], nums[i+1]) != 1:
    	# 서로소가 아니라면 두 수 사이들의 수를 순회하면서
        for j in range(nums[i], nums[i+1]):
            flag = True
            # 두 수와 서로소인 수를 발견하면 cnt += 1
            if _gcd(nums[i], j) == 1:
                if _gcd(j, nums[i+1]) == 1:
                    cnt += 1
                    flag = False
                    break
        # 어떠한 수와도 두 수가 서로소이지 못했다면 cnt += 2
        if flag:
            cnt += 2
print(cnt)