[백준/Python(파이썬)] 17087 숨바꼭질 6

문제

수빈이는 동생 N명과 숨바꼭질을 하고 있다. 수빈이는 현재 점 S에 있고, 동생은 A1, A2, ..., AN에 있다.

수빈이는 걸어서 이동을 할 수 있다. 수빈이의 위치가 X일때 걷는다면 1초 후에 X+D나 X-D로 이동할 수 있다. 수빈이의 위치가 동생이 있는 위치와 같으면, 동생을 찾았다고 한다.

모든 동생을 찾기위해 D의 값을 정하려고 한다. 가능한 D의 최댓값을 구해보자.

입력

첫째 줄에 N(1 ≤ N ≤ 105)과 S(1 ≤ S ≤ 109)가 주어진다. 둘째 줄에 동생의 위치 Ai(1 ≤ Ai ≤ 109)가 주어진다. 동생의 위치는 모두 다르며, 수빈이의 위치와 같지 않다.

출력

가능한 D값의 최댓값을 출력한다.

풀이

최대공약수를 구해서 푸는 문제. 유클리드 호제법을 사용함

수빈이의 위치가 3이고 동생이 1, 7, 11에 위치한 경우

1----(3)----7----11 형태로 위치하고 있음을 알 수 있고

구간별로 2, 4, 4씩 수가 증가함을 알 수 있다.

이 문제는 증가하는 수들의 최대 공약수를 구해서 풀이한다.

소스코드

def gcd(a, b):  # 최대공약수, 유클리드 호제법
    if b == 0:
        return a
    else:
        return dp(b, a%b)

n, s = map(int, input().split())  # n: 동생의 수, s: 수빈이의 현재 위치
a = list(map(int, input().split()))
ans = abs(s-a[0])

if s == 1:
    print(ans)
else:
    for i in range(1, n):
        ans = gcd(ans, abs(s-a[i]))
    print(ans)

Git : github.com/jisun1125/algorithm-problem-solving/blob/main/baekjoon/no_17087.py

문제 : www.acmicpc.net/problem/17087