[백준/파이썬] 2485번

📍백준 2485번 문제

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

코드

import sys
import math
input = sys.stdin.readline
n = int(input())
street = []
tree = set()
result = 0
for i in range(n):
    street.append(int(input()))
    if i != 0:
        num = street[i] - street[i-1]
        tree.add(num)

min_tree = math.gcd(*tree)

for i in range(1, n):
    if min_tree == street[i] - street[i-1]:
        continue
    else:
        temp = ((street[i]-street[i-1]) // min_tree) - 1
        result += temp

print(result)

풀이

최대공약수를 찾아서 푸는게 포인트 !
중복된 값이 있으면 안되므로 가로수 간의 간격을 set에 저장한다.
이후, set에 저장된 값을 gcd 함수를 통해 최대공약수를 구한다.
간격간 최대 공약수로 나누어, 몫 - 1 한 값을 결과값에 더하면 된다!