[BOJ] 2485 | 가로수

문제링크

---

2485 | 가로수

풀이과정

---

python의 math에서 gcd를 데려와서 간단하게 풀어봤다.

입력받은 나무들의 간격을 먼저 구해서 dis_trees에 저장했다.
그리고 그 간격들의 최대공약수를 구하면 문제는 거의 해결한 것과 마찬가지 !

나무들의 간격에 들어갈 수 있는 가로수의 개수를 result에 누적해주면 된다.
들어갈 수 있는 가로수의 개수는 간격 // 최대공약수 - 1을 해주면 구할 수 있다.

코드

---

import sys
from math import gcd

N = int(input())
trees = [int(sys.stdin.readline().rstrip()) for _ in range(N)]
dis_trees = []
for i in range(1, N):
    dis_trees.append(trees[i] - trees[i-1])

value = dis_trees[0]
for i in range(1, len(dis_trees)):
    value = gcd(value, dis_trees[i])

result = 0
for tree in dis_trees:
    result += tree // value - 1

print(result)

결과

---