Python으로 두 수의 시프트된 배수 표 사이 최소 차이 구하기

문제 개요

두 개의 수 p와 q가 주어졌을 때, 각 수의 무한 배수 표(곱셈표)를 서로 다른 값만큼 밀어낸 뒤, 두 표에 속한 임의의 항들 사이의 최소 차이를 구하는 문제입니다. 이때 시프트 양은 각각 r과 s이며, r과 s는 0 이상의 정수여야 합니다.

예시로 이해하기

p = 7, q = 17, r = 6, s = 3이라고 가정해 보겠습니다.

• 7의 배수 표: [7, 14, 21, 28, 35, 42, 49, ...]
• 17의 배수 표: [17, 34, 51, 68, 85, 102, 119, ...]

여기에 각각 시프트를 적용하면 다음과 같습니다.

• 6만큼 시프트한 7의 배수 표: [13, 20, 27, 34, 41, 48, 55, ...]
• 3만큼 시프트한 17의 배수 표: [20, 37, 54, 71, 88, 105, 121, ...]

두 시프트된 표에서 가장 가까운 항끼리의 차이는 20 − 20 = 0입니다. 따라서 정답은 0이 됩니다.

접근 방법

이 문제는 최대공약수(gcd)를 활용하면 아주 간단하게 해결할 수 있습니다. 알고리즘은 다음 세 단계로 구성됩니다.

1. g := gcd(p, q), 즉 p와 q의 최대공약수를 구합니다.
2. difference := |r − s| mod g, 두 시프트 값의 차이를 g로 나눈 나머지를 계산합니다.
3. difference와 (g − difference) 중 더 작은 값을 반환합니다.

동작 원리

시프트된 첫 번째 표의 항은 r + k·p 형태이고, 두 번째 표의 항은 s + m·q 형태입니다(k, m은 0 이상의 정수). 두 항의 차이는 |r − s + k·p − m·q|인데, 정수론의 잘 알려진 성질에 따르면 k·p − m·q로 만들 수 있는 값은 정확히 gcd(p, q)의 모든 배수입니다. 따라서 도달 가능한 최소 차이는 |r − s|를 g로 나눈 나머지이거나, 그 반대 방향에서 접근한 g − difference 중 작은 쪽이 됩니다.

구현 예제

아래 Python 코드로 위 로직을 확인할 수 있습니다.

import math

def get_minimum_diff(p, q, r, s):
    g = math.gcd(p, q)
    difference = abs(r - s) % g
    return min(difference, g - difference)

p = 7
q = 17
r = 6
s = 3
print(get_minimum_diff(p, q, r, s))

입력

7, 17, 6, 3

출력

0

복잡도 분석

이 풀이의 시간 복잡도는 gcd 계산에 지배되므로 O(log(min(p, q)))이며, 추가 메모리 사용량은 O(1)입니다. 배수 표를 실제로 생성하지 않고도 답을 구할 수 있기 때문에 매우 효율적입니다.