[백준 Python] 2485번 가로수

1, 3, 7, 13 에 가로수가 위치한다면 5, 9, 11 위치에 가로수를 3개 더 심어 간격을 맞춰야 한다.

 

# 가로수 일정한 간격으로 추가하기 / 유클리드 호제법

num = int(input())
arr = []
# arr = [0] * num
arrSub = []
result = 0

# from math import gcd
def gcd(a,b):
    if b>a:
        temp = a
        a = b
        b = temp
    while b!=0:
        a, b = b, a%b
    return a

for i in range(num):
    arr.append(int(input()))
    if i != 0:
        arrSub.append(arr[i]- arr[i-1])

arr = list(set(arr))
arr.sort()

GCD = arrSub[0] # 차의 최대공약수 구하기
for i in range(0,len(arrSub)):
    GCD = gcd(GCD,arrSub[i])

for i in arrSub:
    result += i // GCD - 1

print(result)

1. 생각을 해본다면 가로수 끼리의 차이가 일정해야 한다.

2. 하지만 이때 가로수의 차가 가장 작은 놈이 기준이 되며 다른 가로수의 차와 잘 맞아야 한다. ( 2라면 4, 6, 8 은 가능하지만 5, 7 등은 딱 맞아떨어지지 않는다 )

3. 고로 모든 가로수 차이의 최대 공약수를 구하면 되는 문제이다.

★유클리드 호제법 : 최대공약수 구하기

증명하는 방법 한번만 검색해서 보고 바로 쓰면 된다.

a,b 가 있을 때 (a>b)

a 를 b 로 나눈 나머지와 b 와의 최대공약수는 a, b 의 최대공약수와 일치한다.

(a, b 의 최대공약수 = b, a%b 의 최대공약수) 이를 뒤에 것이 0이 아닐 때 까지 반복하면 된다.

(12, 4) -> (4, 0) -> 최대공약수 4

(12, 5) -> (5, 2) -> (2, 1) -> (1, 0) -> 최대공약수 1

 

 

 

 

 

참고: https://yuuj.tistory.com/121