[백준] 17087번 숨바꼭질 6

💡문제접근

• 동생이 있는 위치에서 수빈이의 위치 S를 빼준 값의 절댓값을 리스트에 저장한 다음 리스트에 있는 수의 최대공약수를 유클리드 호제법을 이용해서 구한다.
• 그 다음 리스트에 들어있는 수의 최대공약수를 구해 정답을 출력한다.

💡코드(메모리 : 41968KB, 시간 : 112ms)

import sys
input = sys.stdin.readline

N, S = map(int, input().strip().split())
A = list(map(int, input().strip().split()))

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

li = []
for i in range(len(A)):
    li.append(abs(A[i] - S))

temp = li[0]
for i in range(1, len(li)):
    temp = gcd(temp, li[i])
print(temp)

📌 여러 수의 최대공약수를 구하는 방법

• 두 수의 최대공약수를 구하는 방법은 간단하다. 그렇다면 N개(N≥3)의 수의 최대공약수를 어떻게 구할까? 위의 코드를 발췌해서 이해해보자.

def gcd(a, b):
    while b > 0:
        a, b = b, a % b
    return a
li = []
for i in range(len(A)):
    li.append(abs(A[i] - S))
# 아래 코드를 보면 초항과 반복문을 돌린 수를 최대공약수 함수에 돌려 공통된 최대공약수를 구하는 것을 알 수 있다.
temp = li[0]
for i in range(1, len(li)):
    temp = gcd(temp, li[i])
print(temp)

💡소요시간 : 10m