[백준 17087번] 파이썬 - 숨바꼭질 6

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

17087번: 숨바꼭질 6

 

 

# 조건

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

 

# 접근 방법

• 동생들의 위치와 현재 위치의 차이를 담은 배열을 만들어 준다.
• 이 배열들의 최대 공약수가 D가 될 수 있는 최댓값이다.
• 유클리드 호제법을 이용하여 구해주었다.
• 현재 위치를 기준으로 하면 음수가 발생할 수도 있으니 abs이용
• 다만, 파이썬에는 math.gcd를 이용하여 최대 공약수를 구할 수 있다.

참고
https://cheon2308.tistory.com/entry/Algorithm-%EC%9C%A0%ED%81%B4%EB%A6%AC%EB%93%9C-%ED%98%B8%EC%A0%9C%EB%B2%95-%EC%B5%9C%EB%8C%80-%EA%B3%B5%EC%95%BD%EC%88%98-%EC%B5%9C%EC%86%8C-%EA%B3%B5%EB%B0%B0%EC%88%98

import sys  
sys.stdin = open('input.txt')  
input = sys.stdin.readline  
sys.setrecursionlimit(10**9)  
  
def gcd(arr, result, idx):  
    if idx == len(arr):  
        return result  
    a = result  
    b = arr[idx]  
    while b > 0:  
        a, b = b, a % b  
    idx+=1  
    return gcd(arr, a, idx)  
  
  
N, S = map(int, input().split())  
  
brother = [*map(int, input().split())]  
  
dist = []  
for i in range(N):  
    dist.append(abs(S-brother[i]))  
  
print(gcd(dist, dist[0], 0))

 

math 모듈 사용

import sys  
sys.stdin = open('input.txt')  
input = sys.stdin.readline  
from math import gcd  
  
  
N, S = map(int, input().split())  
  
brother = [*map(int, input().split())]  
  
dist = []  
for i in range(N):  
    dist.append(abs(S-brother[i]))  
  
print(gcd(*dist))