BOJ(백준) 14252[공약수열]

안녕하세요! 😊 오늘은 백준 온라인 저지의 문제 중 하나인 14252번 문제를 함께 풀어보겠습니다. 이 문제는 주어진 숫자들 사이에서 공약수가 1인 숫자를 찾는 문제입니다. 먼저 문제를 해결하기 위한 접근법을 살펴본 후, 정답 코드를 살펴보겠습니다.

 

1. 문제 설명

문제는 주어진 숫자들 사이에 공약수가 1인 숫자를 찾아야 하는데, 두 수 사이에 숫자를 추가하여 인접한 두 수의 공약수를 1로 만드는 방법을 찾아야 합니다.

 

2. 접근법

1. 최대공약수 구하기:

• 두 수의 최대공약수를 구하는 방법으로 유클리드 호제법을 사용합니다.

• 유클리드 호제법은 두 수를 나누었을 때 나머지가 0이 될 때까지 나머지를 구하는 방법입니다.

2. 인접한 두 수의 공약수 확인:

• 주어진 숫자 리스트를 정렬합니다.

• 정렬된 리스트에서 인접한 두 수의 최대공약수를 확인합니다.

• 만약 최대공약수가 1이 아니면, 그 사이에 숫자를 추가하여 최대공약수가 1이 되도록 합니다.

3. 숫자 추가하기:

• 인접한 두 수의 최대공약수가 1이 아닌 경우, 그 사이에 있는 숫자를 확인하여 최대공약수가 1인 경우를 찾습니다.

• 만약 찾지 못하면 두 개의 숫자를 추가하여 최대공약수가 1이 되도록 합니다.

 

이제, 이러한 접근법을 기반으로 문제를 해결하는 정답 코드를 살펴보겠습니다.

 

** 두개의 숫자를 추가하는 이유는? **

네 개의 숫자 중 적어도 두 개는 서로 소인 두 수를 선택할 수 있기 때문입니다.

유클리드 호제법을 이용한 최대공약수 구하기에서, 두 수가 서로 소일 때 그 최대공약수가 1이 됩니다. 예를 들어, 6과 10 사이에 7과 9를 추가한 경우를 보면, 6, 7, 9, 10은 모두 인접한 두 수 사이의 최대공약수가 1이 됩니다:

• gcd(6, 7) = 1 
• gcd(7, 9) = 1 
• gcd(9, 10) = 1 

어떤 두 수  a 와  b 가 주어졌을 때, 그 사이에 두 수  x 와  y 를 추가할 때 다음 조건을 만족하게 선택할 수 있습니다:

• gcd(a, x) = 1 
• gcd(x, y) = 1 
• gcd(y, b) = 1 

이론적으로, 두 개의 수를 선택할 때마다 적절한 서로 소인 수를 선택할 수 있는 이유는 두 수 사이에 충분한 공간이 있기 때문입니다. 예를 들어,  a 와  b  사이의 모든 수를 검토하면, 적어도 두 개의 서로 소인 수를 선택할 수 있습니다.

실제로 이 접근법은 수학적 성질을 활용하는 것이며, 이를 보장하기 위해 몇 가지 수학적 개념을 이해해야 합니다:

1. 서로 소: 두 수가 공약수가 1밖에 없는 경우.
2. 중간 수 선택: 두 수  a 와  b  사이에는 충분히 많은 수가 있어 두 개의 적절한 수를 선택할 수 있음.

따라서, 항상 두 수 사이에 두 개의 수를 추가하여 네 개의 숫자 사이에 인접한 두 수의 최대공약수가 1이 되도록 할 수 있습니다. 이 성질은 수학적 원리에 근거한 것입니다.

************************************

 

3. 정답 코드

import sys
input = sys.stdin.readline

# 숫자 입력 처리
N = int(input())  # N: 숫자의 개수

# 공약수 비교할 숫자 입력 처리(정렬)
nArr = sorted(list(map(int, input().split())))  # nArr: 입력된 숫자들을 정렬하여 저장

# 정답 출력 변수
ans = 0  # ans: 정답을 저장하는 변수

# 공약수 구하는 함수 선언
def gcd(a, b):
    # 유클리드 호제법을 사용하여 최대공약수 구하기
    while a % b != 0:
        tmp = a % b
        a = b
        b = tmp
    return b  # b: 최대공약수

# 인접한 두 수의 공약수가 1인 여부 확인
for i in range(N-1):
    if gcd(nArr[i], nArr[i+1]) != 1:  # 공약수가 1이 아닌 경우
        for j in range(nArr[i] + 1, nArr[i+1]):
            if gcd(nArr[i], j) == 1 and gcd(j, nArr[i+1]) == 1:  # 공약수가 1인 수가 있다면
                ans += 1
                break
            if j == nArr[i+1] - 1:  # 두 수 사이에 공약수가 1인 수가 없다면
                ans += 2

print(ans)

 

4. 코드 설명

 

gcd 함수:

 

• 입력된 두 숫자의 최대공약수를 구하는 함수입니다.

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

• 두 숫자가 서로 나누어 떨어질 때까지 나머지를 구하여 반복합니다.

• 나머지가 0이 되면 최대공약수를 반환합니다.

 

메인 함수:

 

• 수의 개수를 입력받고, 각 수를 리스트 형태로 입력받아 정렬합니다.

• 인접한 두 수의 최대공약수가 1인지 확인합니다.

• 공약수가 1이 아닌 경우, 그 사이에 공약수가 1인 숫자를 추가하여 해결합니다.

• 최종적으로 필요한 숫자의 개수를 출력합니다.

 

** 유클리드 호제법이란? **

유클리드 호제법

유클리드 호제법(Euclidean algorithm)은 두 수의 최대공약수(GCD)를 찾는 효율적인 방법입니다. 이 방법은 두 수를 반복적으로 나누어 나머지가 0이 될 때까지 나머지를 구하는 방식으로 작동합니다. 마지막으로 나머지가 0이 되었을 때, 그 직전의 작은 수가 두 수의 최대공약수가 됩니다.BOJBOJ

1. 단계 1:
• 252를 105로 나눕니다. 몫은 2이고 나머지는 42입니다.
• 식:  252 = 105 \times 2 + 42 
2. 단계 2:
• 105를 42로 나눕니다. 몫은 2이고 나머지는 21입니다.
• 식:  105 = 42 \times 2 + 21 
3. 단계 3:
• 42를 21로 나눕니다. 몫은 2이고 나머지는 0입니다.
• 식:  42 = 21 \times 2 + 0 

마지막 나머지가 0이 되었을 때, 나머지가 0이 되기 직전의 수 21이 두 수 252와 105의 최대공약수(GCD)입니다.

 

***********************

 

5. Github으로 확인

coTest/BOJ/BOJ01_02_04_14252.py at main · pcy4196/coTest