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

 

 

백준 17087번 숨바꼭질 6

문제 바로 가기

---

📌 문제

수빈이는 동생 $N$명과 숨바꼭질을 하고 있다. 수빈이는 현재 점 $S$에 있고, 동생은 $A_1, A_2, \dots, A_N$에 있다.

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

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

 

입력

첫째 줄에 $N(1 \leq N \leq 105)$과 $S(1 \leq S \leq 109)$가 주어진다.

둘째 줄에 동생의 위치 $A_i(1 \leq A_i \leq 109)$가 주어진다.
동생의 위치는 모두 다르며, 수빈이의 위치와 같지 않다.

 

출력

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

 

 

 

📝 아이디어

1. 문제 분석

• 수빈이가 동생들의 위치에 도달하려면 $D$가 수빈이와 동생들 간의 거리의 공통 약수여야 합니다.
• 각 동생의 위치 $A_i$와 수빈이의 위치 $S$를 기준으로 거리 $d_i = |A_i - S|$를 계산합니다.
• 모든 동생의 위치를 방문할 수 있는 $D$는 $d_1, d_2, \dots, d_N$의 최대공약수(GCD)가 됩니다.

 

2. $D$의 역할

• $D$는 수빈이가 이동할 수 있는 단위 거리를 나타냅니다.
• 수빈이는 현재 위치 $S$에서 $S+D, S-D, S+2D, S-2D, \dots$ 형태로만 이동할 수 있습니다.
• 따라서 $D$가 동생의 위치에 정확히 도달하려면

$$|A_i - S| = \mod D = 0 \quad (\text{for all } i )$$

• 즉, 모든 거리 $|A_i - S|$는 $D$의 배수여야 합니다.

 

3. $D$는 거리들의 최대공약수

• 각 동생들의 위치 $A_1, A_2, \dots, A_N$에 대해 $d_i = |A_i - S|$는 서로 다를 수 있습니다.
• $D$가 모든 동생의 위치에 도달하려면 $D$는 $d_1, d_2, \dots, d_N$의 최대공약수여야 합니다.
• 예를 들어, 거리 리스트가 $[6, 9, 15]$ 라면 가능한 $D$의 최댓값은 이 리스트의 공통 약수 $\{1, 3\}$ 중 3입니다.

 

 

 

👩‍💻 나의 답안

1. 거리 계산

• 각 동생의 위치 $A_i$와 수빈이의 위치 $S$의 절대 거리를 계산하여 리스트에 저장합니다.

distances = [abs(pos - s) for pos in positions]

 

2. GCD 계산

• reduce() 함수를 사용하여 거리 리스트에서 모든 요소의 최대공약수를 계산합니다.

result = reduce(math.gcd, distances)

 

3. 전체 코드

import math
from functools import reduce

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

distances = [abs(pos - s) for pos in positions]

result = reduce(math.gcd, distances)
print(result)

 

 

 

✨ 새로 알게 된 점

1. reduce 함수의 활용

functools의 reduce 함수는 리스트와 같은 반복 가능한 객체에서 모든 요소를 하나의 값으로 축소하는 데 매우 유용한 도구라는 점을 알게 되었습니다. 반복문 없이 간단하게 누적 연산(예: 합계, 곱셈, 최대공약수 등)을 처리할 수 있다는 점이 효율적이었습니다.