[ 백준 17087] ( python ) 숨바꼭질 6

 

📚 숨바꼭질 6

 

문제

수빈이는 동생 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

3 3
1 7 11

예제 출력 1

2

예제 입력 2

3 81
33 105 57

예제 출력 2

24

예제 입력 3

1 1
1000000000

예제 출력 3

999999999

 

 

 

✍ 접근

• 누나와 동생 사이의 거리의 최대공약수를 구하는 문제임을 이해

 

오답 코드(시간 초과)

import sys
n,s = map(int, sys.stdin.readline().split())
arr = list(map(int, sys.stdin.readline().split()))
for i in range(n):
    if arr[i]-s < 0:
        arr[i] = abs(arr[i]-s)
    else:
        arr[i] = arr[i]-s
length = min(arr)
while 0 < length:
    for x in arr:
        if x % length != 0 :
            break
    else:
        print(length)
        break
    length-=1

• math.gcd를 사용하기 전 다른 방법으로 풀어보려고 했다.
• 누나와 동생 간의 거리의 절대값을 구해서 arr을 업데이트하고
• 누나와 동생 간의 최소거리가 0 이상일 때 최소거리에서 1씩 빼 가면서 D(length)의 값을 찾는다
  1. 누나와 동생 간의 거리를 D값으로 나눴을 때 맞아 떨어지지 않으면 for문을 끝낸다
  2. 만약 동생과의 모든 거리가 같으면 print(length)로 D 값을 출력한다

 

 

정답 코드

import sys
import math
n,s = map(int, sys.stdin.readline().split())
arr = list(map(int, sys.stdin.readline().split()))
for i in range(n):
    if arr[i]-s < 0:
        arr[i] = abs(arr[i]-s)
    else:
        arr[i] = arr[i]-s
for i in range(1,n):
    arr[0] = math.gcd(arr[0],arr[i])
print(arr[0])

• math 안에 있는 gcd를 이용해서 누나와 동생의 거리들 간의 최대공약수를 찾는다.
• 누나와 동생 간 거리의 절대값을 구해서 arr을 업데이트하는 것 까지는 동일
• 1부터 n까지 새로운 for문을 돌면서
  1. arr[0]을 새로운 최대공약수로 바꿔가면서 이 값과 arr 안에 들어 있는 다른 값을 비교해 궁극적인 최대공약수를 찾고 출력한다

 

 

 

⭐ 배움

• 내 방법으로 푸는 것도 좋지만 문제에서 원하는 풀이 방식이 확고할 때는 고집부리지 말자
• import math. // math.gcd() 를 이용해 최대공약수를 구할 수 있다.