[알고리즘] 백준 17087 파이썬 - 숨바꼭질6 (유클리드 호제법)

 

17087번: 숨바꼭질 6

 

문제

수빈이는 동생 N명과 숨바꼭질을 하고 있다. 수빈이는 현재 점 S에 있고, 동생은 A1, A2, ..., AN에 있다.

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

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

 

 

문제풀이

#01
n,s=map(int,input().split())
arr=list(map(int,input().split()))
if(len(arr)==1):
    print(abs(arr[0]-s))
    quit()
#02
for i in range(len(arr)):
    if(arr[i]<s):
        arr[i]=s-arr[i]
    else:
        arr[i]=arr[i]-s

#03 유클리드 호제법
def gcd(a,b):
    while b>0:
        a,b=b,a%b
    return a
#04
for i in range(len(arr)-1):
    x = gcd(arr[i],arr[i+1])
    arr[i+1]=x
print(arr[-1])

- 최대공약수 즉 유클리드 호제법을 이용하는 것이 문제의 핵심이다.

- 브루트포스 형태로 풀이할 경우 시간 초과가 일어난다.

 

- #01 : 처음 입력받은 값인 n,s와 리스트를 arr에 저장해준다.

           만약 arr의 길이가 1이라면 절댓값 (arr의 값-s)를 해주고 코드를 종료한다.

- #02 : 입력받은 arr 리스트 값을 s를 기준으로 얼마나 떨어져있는지 각각 반영해준다.

           s보다 작은 값은 s에서 빼고 s보다 큰 값은 s를 뺐다. (abs를 사용해도 된다.)

- #03 : 함수 gcd는 유클리드 호제법 즉 a,b의 최대공약수를 구하는 함수이다.

- #04 : for문을 사용해 arr[i]와 arr[i+1]의 최대공약수를 구하여 x에 저장한다.

           x값을 arr[i+1]에 저장한다. 이렇게 for문을 끝까지 돌면 최종적으로

           arr 리스트의 마지막 값에 전체 리스트의 최대공약수가 남게 된다.

           그 값을 출력해주면 된다.

 

 

 

유클리드 호제법

def gcd(a, b):
    while b > 0:
        a, b = b, a % b
    return a

- 최대공약수를 구하는 공식으로, 찾지 않아도 되는 약수를 최대한 구하지 않기에

  시간을 최대한 단축할 수 있다.

 

 

+ 최소공배수 구하기

(최소공배수 x 최대 공약수) = a * b
최소공배수 = a * b / 최대 공약수

즉 최소공배수는 서로 다른 수 a,b의 곱을 최대 공약수로 나눈 것이다.

파이썬 코드로는 아래와 같이 표현할 수 있다.

def lcm(a, b):
    return a * b / gcd(a, b)