[백준] 17087번 : 숨바꼭질 6 (Python)

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

 

동생을 찾기 위해 이동할 수 있는 최대 거리 D를 구하는 문제다.

 

import sys

# 유클리드 호제법으로 최대공약수 구하기
def gcd(N, M):
    
    if(M == 0):
        return N
    
    return gcd(M, N%M)

input = sys.stdin.readline
N, S = map(int, input().split()) # 동생 N, 수빈이 위치 S
case = list(map(int, input().split())) # 동생 위치 S
dis = []
    
for i in case:
    dis.append(abs(S-i)) # 동생과의 거리 S

answer = dis[0]
for i in dis[1:]:
    answer = gcd(answer, i) # 최대 공약수 구하기
print(answer)

 

 

 

[문제풀이]

---

 

빈이는 동생 N명과 숨바꼭질을 하고 있다. 수빈이는 현재 점 S에 있고, 동생은 A1, A2, ..., AN에 있다.
수빈이는 걸어서 이동을 할 수 있다. 수빈이의 위치가 X일때 걷는다면 1초 후에 X+D나 X-D로 이동할 수 있다. 수빈이의 위치가 동생이 있는 위치와 같으면, 동생을 찾았다고 한다.
모든 동생을 찾기위해 D의 값을 정하려고 한다. 가능한 D의 최댓값을 구해보자.

 

 

문제 설명이 좀 개떡같이 되있어서 처음엔 이해를 못했다.

한번에 이동할 수 있는 거리가 D, 그 D 거리 이동해서 동생들을 찾아내야 하는 문제다.

D 거리를 갔다가 다음엔 R거리를 갔다가 그럴수가 없고, 동생을 찾으러 A1으로 이동한 후에 찾는것이 아닌 S 위치에 고정되서 찾는것.

 

 

 

 

그래서 현재 수빈이의 위치에서 각 동생까지의 거리를 빼서 구한 값, 이 값의 최대 공약수를 구해주면 되는 문제.