[백준] 2485: 가로수 - 파이썬[python]

풀이

1. 나는 속도를 위해 sys와 dictionary를 사용하였다.
2. 가로수끼리의 간격을 dic에 value값으로 저장하였다.
3. 저장한 가로수 간격들의 최대공약수를 구한다.
   • 이때 최대공약수를 갱신할 때 이전의 gcd 값과 최대공약수를 구해야 할지 해당 가로수 간격값과 구해야 할지 고민했었다.
4. 심어야 할 가로수의 수는 또다시 dic를 돌면서 간격에서 최대공약수를 나누고 -1을 해준 값들의 합이다.
   • 이렇게 하면 모든 가로수들의 간격이 똑같아 가로수를 더 심어도 되지 않을 때도 0이 잘 출력된다.

코드

import sys, math

N = int(sys.stdin.readline())
gap = {}
result = 0

b = int(sys.stdin.readline())
for i in range(N-1):
    a = b
    b = int(sys.stdin.readline())
    gap[i] = b-a

gcd = gap[0]
for i in range(1, len(gap)):
    gcd = math.gcd(gcd, gap[i])

for i in gap:
    result += gap[i] // gcd - 1

print(result)

결과

고민하다 떠올린 방법이 조금 복잡해서 다른 방법이 있나 했는데, 다른 사람들과 똑같은 방법이었다🥹