[백준 알고리즘/Python] 17087 숨박꼭질6

문제

 

문제 이해

수빈이의 위치 S에서 각 동생의 위치의 절대값을 구하면 수빈이가 얼마나 이동해야하는지 알 수 있습니다.

ex) 수빈이가 3에 있고 동생이 1, 7 11에 있으니 [ 2, 4, 8 ]만큼 움직이면 됩니다. 

[ 2, 4, 8 ]에서 시간을 고려하지 않고 모든 동생을 찾으려면 2씩 움직이면 됩니다.

즉, [ 2, 4, 8 ]에서 최대공약수를 구하면 됩니다.

 

 

코드

N,S = map(int,input().split())
children = list(map(int,input().split()))
li = []
result = 0
def 최대공약수(num1, num2):
    #num1이 num2보다 크게
    if(num1 < num2):
        a = num1
        num1 = num2
        num2 = a

    while((num1 % num2 != 0)):
        temp = num2
        num2 = (num1 % num2)
        num1 = temp

    return num2

for i in range(N):
    li.append(abs(children[i] - S))

result = li[0]
for j in range(1,len(li)):
    result = 최대공약수(result,li[j])
    
print(result)

최대공약수(2,4,8)을 구하는건 최대공약수(최대공약수(2,4),8)과 같습니다.

result에 첫 번째 동생과의 걸이를 구한 후 다음 동생거리를 최대공약수로 구해주면 됩니다.

ex) 최대공약수(2,4) -> 최대공약수(2,8)이 되겠지요