[Python] 백준 #14252 공약수열 - Platinum 5

문제 링크

https://www.acmicpc.net/problem/14252

 

문제

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

입력

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

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

출력

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

힌트

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

---

해결 방법

인프런 강의(2주만에 통과하는 알고리즘 코딩테스트)에서 정수론을 활용한 최적화 강의에서 공약수를 구하는 것을 배웠다.

인접한 두 수가 서로소가 될 수 있도록 사이에 1개 혹은 2개의 숫자를 추가해주면 된다!

for i in range(A+1,B):
  if gcd(A,i) ==1:
    if gcd(B,i) == 1:
      count +=1
      break
  if i == (B-1):
    count += 2

 

배열의 앞에서부터 연속된 숫자가 서로소라면 OK

만약에 서로소가 아니라면 A+1부터 반복하며 A와 B 각각과 서로소가 되면 1개 추가

사이에 있는 모든 수를 봐도 gcd(A, i) == 1 과 gcd(B, i) == 1를 모두 만족하는 i가 없다면 2개 추가

이 과정을 집합에서 순회하면 된다.

 

최종 코드

import sys
input = sys.stdin.readline

def gcdlist(nums):
    count = 0
    nums = sorted(nums)
    for idx in range(len(nums)-1):
        A, B = nums[idx:idx+2]
        if gcd(A,B)!=1:
            count += check_gcd(A,B)
            
    return count


def check_gcd(a,b):
    for i in range(a+1,b):
        if gcd(a,i)==1:
            if gcd(b,i)==1:
                return 1
    return 2
        
def gcd(a,b):
    while a%b!=0:
        temp = a%b
        a=b
        b=temp
    return b


N = int(input())
nums = list(map(int,input().split()))
print(gcdlist(nums))

 

간략하게나마 증명하려했지만, B>A+3일 때, A+1, B-1을 추가한다고 귀납적 증명이 되지 않는다는 것을 깨달았다..

그렇다면, 왜 두 수 A와 B 사이에 1개 혹은 2개만 추가해준다면 연속된 숫자는 모두 서로소가 될 수 있을까? 이를 증명해보겠다!

 

전제 조건

A와 A+1 (A>1)는 항상 서로소이다.

 

증명 과정

B=A+3일때만 본 증명을 보이면 B>A+3일 때는 항상 가능하다는 것을 알 수 있다. (이는 귀납적 증명을 통해 알 수 있으니 생략)

[A, A+2( = B - 1), B( = A + 3) ]

- A가 짝수라면 A와 A+2는 서로소가 아니다.

- A가 홀수라면 A와 A+2, A+2와 A+3 은 각각 서로소가 아니다. -> 1개만 추가하면 된다.

 

[A가 짝수일 때, A, A+1, A+2]

- 전제 조건을 통해 A가 짝수라면 A+1, A+2 2개를 추가하면 된다.

 

즉,  "A+1와 B-1" 최대 2개를 추가하면 연속된 수들은 모두 서로소가 가능해진다.