문제링크



해결방안
1)가로수 위치를 나타내는 정수가 무진장 많으므로 sys 라이브러리 사용하기 

2)나무 위치간 간격을 list로 저장하고 그 list의 모든 수에 대한 최대 공약수 사용하기


내 방안


1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
import math
import sys
 
n=int(sys.stdin.readline())
#나무 위치간 거리
d=[]
 
#나무 위치사의 거리 (모르니까 0으로 초기화)
now=0
 
# 반복문 하나로 나무 위치간 거리 구하기
for i in range(n):
    k=int(sys.stdin.readline())
    #처음 집어 넣을때는 거리를 구할 수 없으므로 나무 위치값만 int로 저장
    if i==0:
        now=k
    else:
        d.append(k-now)
    now=k
 
# 나무 간격 거리 구한 list(d)를  solution 함수에 집어 넣기 
# 해결 방안 
# 1)거리 간격이 저장된 list(d)의 모든 최대공약수를 구하기
# 2) 1에서 구한 값을 list(d)에 있는 각각의 수에 나누고 1 을 뺀값을 더하면서 갱신하기
def solution(d):
    answer = 0
    min_l=d[0]
    for i in d[1:]:
        min_l=math.gcd(min_l,i)
    for i in range(len(d)):
        answer +=d[i]//min_l-1    
    return answer
print(solution(d))
 
 
 
         
cs


처음에는 나무 위치 리스트와 거리 리스트 2개로 풀었지만 굳이 나무 위치 리스트를 저장할 필요가 없다 판단해서
거리 리스트만 저장하여 해결함



sys라이브러리  사용 여부에 따라 속도 약 39배 차이남

오랜만에 백준 푸니까 재밌음
빨리 골드 3 가야겠음