[백준 17087 파이썬/python] 숨박꼭질 6

숨바꼭질 6

문제

입력

출력

예제 입력 1

예제 출력 1

예제 입력 2

예제 출력 2

예제 입력 3

예제 출력 3

풀이

1)

2)

숨바꼭질 6

시간 제한	메모리 제한	제출	정답	맞힌 사람	정답 비율
1 초	512 MB	8041	3981	3192	48.503%

문제

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

풀이

1)

from math import gcd

N, S = map(int, input().split())  # N : 동생 수, S : 수빈이의 위치
A_list = list(map(int, input().split()))  # A_list : 동생들의 위치
distance = []  # 수빈이와의 거리
for x in A_list:
    distance.append(abs(S - x))

if len(distance) == 1:
    x = distance[0]
else:
    x = gcd(distance[0], distance[1])
    for i in range(2, len(distance)):
        y = gcd(x, distance[i])
        x = y
print(x)

2)

def gcd(x, y):
    if y == 0:
        return x
    else:
        return gcd(y, x%y)
n, s = map(int,input().split())
a = list(map(int,input().split()))
a = [abs(x-s) for x in a]
ans = a[0]
for i in range(1, n):
    ans = gcd(ans, a[i])
print(ans)

두 번째 코드가 훨씬 가독성도 좋고 깔끔하므로 두 번째 코드에 대한 풀이만 작성하겠습니다.

• 풀이과정
  1. 먼저, gcd 함수를 재귀를 사용하여 정의합니다. 이 함수는 두 정수 x와 y를 인자로 받아 그 최대공약수를 반환합니다.

  def gcd(x, y):
      if y == 0:
          return x
      else:
          return gcd(y, x%y)

  1. 수빈이의 동생 수(n)와 수빈이의 위치(s)를 입력 받습니다.

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

  1. 동생들의 위치를 입력 받아 정수로 변환한 뒤 리스트로 저장합니다.

  a = list(map(int, input().split()))

  1. 수빈이와 동생들 사이의 거리를 계산하여 리스트 컴프리헨션을 사용하여 a 리스트를 업데이트합니다.

  a = [abs(x-s) for x in a]

  1. 첫 번째 거리를 ans 변수에 저장합니다.

  ans = a[0]

  1. a 리스트에 있는 나머지 거리들과의 최대공약수를 순차적으로 구합니다.

  for i in range(1, n):
      ans = gcd(ans, a[i])

  1. 마지막으로 최대공약수를 출력합니다.

  print(ans)

  이렇게 코드를 실행하면 수빈이와 동생들 사이의 거리들의 최대공약수가 계산되어 출력됩니다.

Uploaded by N2T