[백준] 2485번: 가로수/ 파이썬

문제 링크

---

https://www.acmicpc.net/problem/2485

2485번: 가로수

풀이 코드

---

import sys
from math import gcd

N = int(sys.stdin.readline())

a = int(sys.stdin.readline())

arr = []

for i in range(N-1):
    num = int(sys.stdin.readline())
    arr.append(num - a)
    a = num

g = arr[0]
for j in range(1, len(arr)):
    g = gcd(g, arr[j])

result = 0
for each in arr:
    result += each // g - 1
print(result)

코드 해석

---

가로수들 사이의 값을 저장할 배열을 만든 뒤 가로수들 사이의 간격 저장한다.
arr에 들어있는 모든 수들의 최대공약수 찾은 후 둘 사이에 심을 가로수 개수를 찾는다.

개수 = 간격 // 최대공약수 - 1