[백준/BOJ] 2485번 가로수 (Python)

[백준/BOJ] 2485번 가로수

www.acmicpc.net/problem/2485

2485번: 가로수

 

이 문제는 최대공약수를 이용하는 문제였다. 여러 수의 최대공약수를 구해본적이 없어서 찾아봤는데, 두 수 간의 최대공약수를 구하고, 그 수로 다음수와의 최대공약수를 구하는 방식이 있어서 그 방식으로 문제를 풀었다.

처음에는 시간초과가 나왔는데, 각 나무의 간격을 리스트에 저장하고, 그 리스트의 값 간의 최대공약수를 구하면 값을 빼는 방식으로 코드를 짜서 pop을 많이 사용하다 보니 시간초과가 난 것 같다.

그래서 리스트를 따로 만들지 않고, 변수만 사용해서 문제를 다시 풀었다.

 

알고리즘

1. n과 trees를 입력받는다

2. 입력받은 trees의 두번째 값에서 첫번째 값을 뺀 값을 gcd에 넣는다 (첫번재 나무와 두번째 나무의 거리)

3. 2부터 n까지 반복문을 돌면서 앞의 간격(gcd)와 뒤의 간격(g)의 최대공약수를 구해 gcd에 넣는다.

4. trees의 마지막 값에서 첫번째 값을 빼서 길이를 구한 뒤, gcd로 나누고 n-1를 빼서 추가로 심어야 하는 나무의 수를 구한다.

 

Python code

n=int(input())
trees=[int(input()) for _ in range(n)]

gcd=trees[1]-trees[0]
for i in range(2,n):
  g=trees[i]-trees[i-1]
  while g:
    temp=gcd%g
    gcd=g
    g=temp

cnt=(trees[-1]-trees[0])//gcd-(n-1)
print(cnt)