17087번 숨바꼭질 6 : 파이썬(python)

17087번 숨바꼭질 6 : 파이썬(python)

https://www.acmicpc.net/problem/17087

 

 

 

문제

---

수빈이는 동생 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값의 최댓값을 출력한다.

 

 

 

문제 요소 찾기

---

1. S가 D[i]보다 크면 S - D[i]만큼 이동! 

2. S가 D[i]보다 작으면 D[i]를 S만큼 감소

3. 동생을 찾을 경우는 그냥 지워주면 됨.(이동할 필요가 없으니까)

 

여기서 나온 값들의 최대공약수 중 제일 작은 값이 모든 동생을 찾기 위한 d의 최대값이다. 

(모두를 탐색해야 하니까!)

 

 

최종 완성 코드

---

def gcd(a, b):
    
    if(b == 0):
        return a
    return gcd(b, a%b)


N, S = map(int, input().split())
D = list(map(int, input().split()))

li = []
    
for i in range(len(D)):
    if D[i] < S:
        D[i] = S - D[i]
    elif D[i] > S:
        D[i] -= S
    else :
        del D[i]

for i in range(len(D)):
    li.append(gcd(D[i], D[i-1]))

print(min(li))

 

 

봐주셔서 감사합니다. 피드백이나 질문은 댓글 달아주시면 답변 드리겠습니다!