Python으로 두 수를 서로소가 아니게 만드는 최소 연산 횟수 구하는 방법

두 개의 자연수 A와 B가 주어집니다. 한 번의 연산에서는 두 수 중 아무거나 하나를 선택해 1만큼 증가시키거나 1만큼 감소시킬 수 있습니다. 이때 A와 B의 최대공약수(GCD)가 1이 되지 않도록, 즉 두 수가 서로소(coprime) 관계가 아니게 만드는 데 필요한 최소 연산 횟수를 구하는 것이 이 글의 목표입니다.

예를 들어 입력이 A = 8, B = 9라면 정답은 1입니다. 9를 선택해 10으로 바꾸면 8과 10의 최대공약수는 2가 되어 두 수가 더 이상 서로소가 아니기 때문입니다.

문제 해결 접근 방식

이 문제는 경우의 수를 몇 가지로 나누어 생각하면 간단하게 해결할 수 있습니다.

1. 이미 서로소가 아닌 경우: gcd(A, B)가 1이 아니라면 어떤 연산도 필요하지 않으므로 0을 반환합니다.
2. 둘 중 하나가 짝수인 경우: 최대공약수가 1인데 한쪽이 짝수라면 다른 한쪽은 반드시 홀수입니다. 이때 홀수인 수를 1만큼 증가 또는 감소시켜 짝수로 만들면 두 수 모두 2로 나누어떨어지므로 최대공약수가 최소 2가 됩니다. 따라서 1을 반환합니다.
3. 둘 다 홀수인 경우: 먼저 한쪽을 ±1 했을 때 상대방과의 최대공약수가 1이 아니게 되는지 확인합니다. 가능하다면 1을 반환하고, 그렇지 않다면 양쪽을 각각 짝수로 만들면 되므로 2를 반환합니다.

참고로 두 수가 모두 홀수일 때에도 정답은 절대 2를 넘지 않습니다. 홀수는 항상 한 번의 연산으로 짝수로 만들 수 있고, 두 수가 모두 짝수가 되면 최대공약수가 최소 2가 되기 때문입니다.

구현 예제

from math import gcd

class Solution:
    def solve(self, a, b):
        # 이미 서로소가 아니면 연산 불필요
        if gcd(a, b) != 1:
            return 0
        # 둘 중 하나라도 짝수면 한 번의 연산으로 해결 가능
        if a % 2 == 0 or b % 2 == 0:
            return 1
        else:
            # 둘 다 홀수인 경우: 한 번의 연산으로 가능한지 확인
            if (gcd(a + 1, b) != 1 or gcd(a - 1, b) != 1
                    or gcd(a, b - 1) != 1 or gcd(a, b + 1) != 1):
                return 1
            else:
                return 2

ob = Solution()
A = 8
B = 9
print(ob.solve(A, B))

입력

8, 9

출력

1