[Baekjoon]백준 2485 가로수(실버 4) - Python

문제설명

예제

문제를 살펴보면 n을 입력받아 n개의 가로수 위치를 입력받고

사이사이에 간격이 일정하도록 심어야 하는 가로수의 최소값을 구해야한다 

그렇다면 입력 받은 값 사이의 거리들 중 가장 작은 값을 구해야하는 것으로 생각할 수 있지만, 아니다

왜냐하면 가로수 사이 거리가 2 4 5 와 같다면 이들 사이의 일정 거리는 2가 아니라 1이 되기 때문이다

그래서 이걸 구하기 위해서는 각 거리들 사이의 최대공약수를 찾아야한다

 

배열 두개를 만들어 하나는 가로수의 위치, 하나는 가로수끼리의 거리를 저장한다

그리고 가로수끼리의 거리끼리의 최대공약수를 찾아준다

최대공약수를 찾았다면 가로수의 위치에 최대공약수를 더한 값이 존재하는지 확인하거나,

거리를 최대공약수로 나누어 몫을 저장하는 방법도 있다

 

필자는 후자로 선택하여 코드를 작성하였다 대신 몫을 바로 저장하면 안되고 -1을 해주어야한다

최대공약수가 2일때 만약 거리가 2 4 4 와 같다면 2인 경우는 이미 가로수가 존재하기 때문에 심어야하는 가로수에 포함되지 않기 때문이다 그래서 몫에서 1을 뺀 값을 심어야하는 가로수에 더해주면 된다

import math

tree = []
tree_interval = []
n = int(input())

for _ in range(n):
    dis = int(input())
    tree.append(dis)
    
for i in range(len(tree) - 1):
    tree_interval.append(tree[i+1] - tree[i])
    
gcd = tree_interval[0]
for i in range(1, len(tree_interval)):
    gcd = math.gcd(gcd, tree_interval[i])
    
cnt = 0
for i in range(len(tree_interval)):
    s = tree_interval[i] // gcd - 1
    cnt += s
    
print(cnt)