[백준]2485번: 가로수 파이썬

https://www.acmicpc.net/problem/2485

 

간격이 다른 여러 가로수 사이에 추가로 가로수를 심어 일정한 간격으로 맞추는 문제. 이때 최소한으로 가로수를 추가해야 한다.

문제를 풀기 위해선 최대공약수(GCD) 사용한다. 각 가로수 사이의 간격들을 모두 동일하게 맞춰야 하니까 모든 간격들의 최대공약수를 구하고 그 간격을 기준으로 추가 가로수를 심으면 된다.

 

풀이

import sys
def gcd(x, y):
  while y > 0:
    x, y = y, x%y
  return x
n = int(sys.stdin.readline())
tree = []
loc = int(sys.stdin.readline())
first =loc
for _ in range(n-1):
  loc2 = int(sys.stdin.readline())
  tree.append(loc2-loc)
  loc = loc2
  if len(tree) == 2:
    x = gcd(tree[0], tree[1])
    tree = [x]
if n == 1:
  print(0)
elif (loc-first)%tree[0] > 0:
  print((loc-first)//tree[0] - n + 2)
else:
  print((loc-first)//tree[0] - n +1)

1. `gcd` 함수는 두 수의 최대공약수를 구하는 함수. 유클리드 호제법을 사용.
2. 첫 번째 가로수 위치를 저장하고, 그 이후 가로수들 사이의 간격을 계산해 리스트에 저장.
3. 가로수 사이 간격 두 개씩 최대공약수를 구해 나가면서 간격을 하나로 줄여나감.
4. 마지막으로 모든 가로수 사이의 간격이 동일할 때, 첫 가로수와 마지막 가로수 간 거리를 최대공약수로 나눈 값에서 기존 가로수 개수를 빼고 추가로 심어야 할 가로수 개수를 계산.


- 가로수가 한 그루면 더 이상 가로수를 심을 필요가 없으니 0을 출력.
- 간격을 최대공약수로 나누어 남은 간격만큼 가로수를 추가로 심을 수 있는지를 확인해 결과를 출력.