⚠︎ 백준 - 2485 가로수

약수, 배수와 소수 2

단계를 끝내자~2문제 남음

---

 

모든 가로수가 같은 간격이 되도록 새로 심어야 하는 가로수의 최소수 

구하기~

 

보니까 첫 번째 가로수와 시작점의 길이는 상관 없으므로첫번째나무-마지막 나무 사이의 거리가 찐임

 

그 사이에 드문드문 나무로 간격이 나눠져 잇으니간이 간격들의 최대공약수 구하면 그게 최종 간격~!~!~

 

근데 그럼 간격 2,3같이 서로소는 양의 정수로 나타낼 수 없는 게 아닌가가 아니고~ 1로 되고~멍청~

 

은 와~!~!~!~! 시간초과를 냈다!!!이건 말도안되는처사다

 

으으ㅇㅡ생각해보니 이걸

result = 0
treeHere = trees[0]
while True :
    if treeHere not in trees :
        result += 1
    treeHere += gap

    if treeHere > trees[-1]:
        break

매 간격마다 잇는지 체크하지 말고

result = 0
distance = trees[-1] - trees[0]
print(((distance // gap) + 1) - N)

길이 나누기 갭 해서 원래 있던 나무들 개수만 없애면 되네 ^^;;

 

낑..실4...

---

유클리드 호제법

def gcd(a, b):
    while b > 0:
        a, b = b, a % b
    return a

한줄!