[백준 문제풀이] 2485 - 가로수

백준 문제풀이 2485번

풀이

1. 입력받은 가로수 간 간격을 저장하는 gapList를 만든다
2. gapList 요소들의 최대공약수를 구해준다
3. 최소수를 구한다

코드

import sys

input = sys.stdin.readline

N = int(input())

# 가로수 크기, 가로수 간격을 저장하고 정렬
gapList = [0] * (N - 1)
gap = int(input())
for i in range(N - 1):
    num = int(input())
    gapList[i] = num - gap
    gap = num


# 최대공약수
def gcd(a, b):
    while b > 0:
        a, b = b, a % b
    return a


isGcd = gapList[0]
for i in range(1, len(gapList)):
    isGcd = gcd(isGcd, gapList[i])

# 최소수
cnt = 0
for i in range(len(gapList)):
    cnt += gapList[i] // isGcd - 1

print(cnt)