백준 17087 문제 분석 python

이게 최대공약수 문제라고..?

🐒 숨바꼭질 6

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

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

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

• 첫째 줄에 N(1 ≤ N ≤ 10^5)과 S(1 ≤ S ≤ 10^9)가 주어진다. 둘째 줄에 동생의 위치 Ai(1 ≤ Ai ≤ 10^9)가 주어진다. 동생의 위치는 모두 다르며, 수빈이의 위치와 같지 않다.
• 가능한 D값의 최댓값을 출력한다.

동생이 10^5명이라고..?

입력 예시

3 3
1 7 11

출력 예시

2

✍ 나의 풀이

def gcd(x,y):
    if y>x:
        x,y=y,x
    while y > 0:
        x= x%y
        x,y = y,x
    return x

n,s  = map(int,input().split())

arr = list(map(int,input().split()))

distance = []
for i in arr:
    x = s - i
    if x == 0:
        continue
    elif x < 0 :
        x *= -1
    distance.append(x)

ans=distance[0]
for i in range(1,n):
    ans=gcd(distance[i],ans)

print(ans)

인터넷보고 저렇게 제출하니 정답이긴한데
처음 제출할땐 문제 이해를 못해서 그냥 거리가 최소이면 답인갑다 하면서 제출했는데 오답이었다.

동생들과의 거리들의 최대 공약수가 답이라는데 왜일까..

인터넷을 찾아도 왜 최대공약수 문제인지 안나온다..

일단 번잡한 나의 코드부터 최적화 해봐야겠다.

def gcd(x,y):	#math라이브러리 에서 math.gcd()써도됌
    if y>x:		#대소비교 필요없음 어차피 나머지 연산 반복문에서 해결됌 
        x,y=y,x
    while y > 0:
        x= x%y
        x,y = y,x
    return x

n,s  = map(int,input().split())

arr = list(map(int,input().split()))

distance = []
for i in arr:	
    x = s - i
    if x == 0:	#거리가 0이면 gcd에서 제외됌
        continue
    elif x < 0 :	#절댓값함수 abs() , absolute value
        x *= -1
    distance.append(x)	

ans=distance[0]
for i in range(1,n):
    ans=gcd(distance[i],ans)

print(ans)

정리하면

import math

n,s  = map(int,input().split())

arr = list(map(int,input().split()))

distance = []
for i in arr:
    distance.append(abs(s - i))

ans=distance[0]
for i in range(1,n):
    ans=math.gcd(distance[i],ans)

print(ans)

문제 이해

문제에서 구하는 D를 간격, 보폭으로 인식

입력
3 81
33 105 57

출력
24

3은 동생 인원수, 81은 자기 위치
33 105 57은 동생들 위치

81위치에서 보폭을 24로 가지면 모든 동생들한테 갈수있음

이는 자신과 각 동생의 거리가
48 24 24
이 셋의 최대공약수가 24이기에 D의 최대값은 24가 될 수 있음

최소거리를 구하는 문제가 아님
위에선 단순히 최소거리를 구해도 24가 나오지만

입력
3 10
1 6 13

이런 상황에서는 최소거리가 3이지만 당연히 모든 동생에 접근 할 수없으므로 답이 되지 못한다.