[백준] 1684번 같은 나머지

💡문제접근

• 정수 N을 정수 D로 나눴을 때 몫을 Q, 나머지를 R이라고 하고 나머지 정리에 의해 식을 세워보면 N = Q × D + R을 만족하게 된다. 모든 정수를 한 정수 D로 나눴을 때 나머지가 같아지는 가장 큰 D를 구하는 문제인데 결국 구하고자 하는 D는 최대공약수와 관련이 있다.

💡코드(메모리 : 31256KB, 시간 : 40ms)

import sys
input = sys.stdin.readline

N = int(input())
lst = list(map(int, input().strip().split()))
Min = min(lst)

def GCD(a, b):
    if a < b:
        a, b = b, a
    while b != 0:
        a, b = b, a % b
    return a

result = []
for i in range(N):
    if lst[i] != Min:
        result.append(lst[i] - Min)

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

💡소요시간 : 28m