[백준/Python] 2485번 가로수 문제

■ 2485번 가로수 문제

 

출처: 백준 2485번 가로수 문제

 

 

■ 코드 풀이

 

백준 문제를 풀면서 정말 많이 배우는 것 같습니다. 파이썬 math에는 gcd라는 함수가 있는데요. 이 gcd 함수는 두 수의 최대 공약수를 구해준다고 합니다. 가로수 간격의 최대 공약수를 어떻게 구해야 하지 하면서 고민하고 있었는데 단번에 고민 해결이네요. 역시 세상에 코딩 고수들은 정말 많은 것 같습니다.

참고로 최대 공약수 이외에도 최소 공배수를 구해주는 함수도 있다고 합니다. 관련 링크는 코드 아래에 넣어 두었으니, 궁금하신 분들은 한번 들어가 보시는 것도 나쁘지 않아 보입니다.

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)

 

 

https://blockdmask.tistory.com/525

[python] 파이썬 최대공약수, 최소공배수 함수 (gcd, lcm)