[알고리즘] 백준 2485 파이썬 - 가로수

 

2485번: 가로수

 

문제

직선으로 되어있는 도로의 한 편에 가로수가 임의의 간격으로 심어져있다. KOI 시에서는 가로수들이 모두 같은 간격이 되도록 가로수를 추가로 심는 사업을 추진하고 있다. KOI 시에서는 예산문제로 가능한 한 가장 적은 수의 나무를 심고 싶다.

편의상 가로수의 위치는 기준점으로 부터 떨어져 있는 거리로 표현되며, 가로수의 위치는 모두 양의 정수이다.

예를 들어, 가로수가 (1, 3, 7, 13)의 위치에 있다면 (5, 9, 11)의 위치에 가로수를 더 심으면 모든 가로수들의 간격이 같게 된다. 또한, 가로수가 (2, 6, 12, 18)에 있다면 (4, 8, 10, 14, 16)에 가로수를 더 심어야 한다.

심어져 있는 가로수의 위치가 주어질 때, 모든 가로수가 같은 간격이 되도록 새로 심어야 하는 가로수의 최소수를 구하는 프로그램을 작성하라. 단, 추가되는 나무는 기존의 나무들 사이에만 심을 수 있다.

 

문제풀이

#최대공약수 함수
def gcd_func(a,b):
    while b!=0:
        a,b = b, a%b
    return a
n= int(input())
List=[]
a=0
b=0
for i in range(n):
    x = int(input())
    if(a==0):
        a=x
    else:
        b=x
        List.append(b-a)
        a=b
#List의 중복을 제거한 리스트
List_set = list(set(List))
#초기값은 첫번째 값
gcd=List_set[0]
for i in range(1,len(List_set)):
    #구한 gcd와 그 다음 값을 계속 비교해서 최종 gcd를 구함
    gcd = gcd_func(gcd,List_set[i])
#가로수 개수
cnt=0
for k in List:
    #각각 간격을 최대공약수로 나누고 1을 빼주면 심을 가로수 개수
    cnt += k//gcd -1
#최종적으로 심을 가로수 개수
print(cnt)

 

코드설명

- x값을 입력받고 초기값이 없으면 a에 저장, 있다면 b에 저장한다.

- 이후 b-a 즉 가로수 사이의 간격을 List에 추가한다. 

- 추가 후 b를 초기값인 a에 저장하고 for문이 끝날 때 까지 해당 과정을 반복한다.

- 그 결과 가로수 사이의 간격을 나타낸 List가 완성된다.

- 완성된 List에서 중복된 값을 제거해준다.

- 이후 최대공약수를 과정에 거쳐 구해준다.

- 최종적으로 간격을 최대공약수로 나누고 1을 빼주면 간격마다 심어야 할 가로수 개수가 나온다.

- 모두 더한 후 최종적으로 심을 가로수 개수를 출력해준다.