https://www.acmicpc.net/problem/2485
최종 코드
import math
import sys
n = int(sys.stdin.readline())
tree = []
for i in range(n):
tree.append(int(sys.stdin.readline()))
diff = tree[1] - tree[0]
for i in range(2,len(tree)):
diff = math.gcd(diff, tree[i] - tree[i - 1])
print((tree[-1] - tree[0]) // diff - (n - 1))
이전 코드(메모리초과)
import math
import sys
n = int(sys.stdin.readline())
tree = []
for i in range(n):
tree.append(int(sys.stdin.readline()))
diff = 100000
for i in range(1,len(tree)):
temp = abs(tree[i-1] - tree[i])
if temp < diff:
diff = temp
for i in tree:
temp = diff
gcd = math.gcd(temp, i)
if gcd != 1 and diff > gcd:
diff = gcd
ans = set(i for i in range(tree[0],tree[-1] + 1,diff))
tree = set(tree)
print(len(ans - tree))
이전에는 배열 전체를 돌린 후 set을 이용한 차집합을 활용해 남은 집합의 갯수를 통해 구현하였다.