백준 알고리즘 2485번: 가로수 (Python)

문제 정보

---

 

2485번: 가로수

 

핵심

---

 

최대공약수 문제다! 라는 것을 빠르게 캐치하여야 함

일일히 최대공약수를 구하는것은 정말 비효율적이니, 유클리드 호제법을 통해서 구하는 것이 올바른 풀이이다

각 가로수의 간격들의 전체 최대공약수를 구하고 이 간격에서 비어있는 가로수의 개수를 찾아서 출력해주면 된다

 

 

풀이

---

from sys import stdin

N = int(stdin.readline())
tree = list(map(int, stdin.readlines()))

def GCD(a, b):
    r = a % b
    if r == 0:
        return b
    return GCD(b, r)

tmp = tree[1] - tree[0]
for i in range(1, N-1):
    tmp = GCD(max(tmp, tree[i+1] - tree[i]), min(tmp, tree[i+1] - tree[i]))
    if tmp == 1:
        break

print(((tree[-1] - tree[0]) // tmp + 1) - len(tree))

 

일단, 배열 tmp 에는 먼저 두번째 가로수와 첫번째 가로수의 간격 차이를 넣어놓고

그 다음 수들의 간격과 최대공약수 연산을 하고 tmp 에 다시 저장한다

이후에는 이전의 최대공약수와 다음 간격간의 최대공약수를 계속 구해나간다

 

만약 1이 되면, 어차피 이후 연산에서의 최대공약수는 1이기에 break 하고 결과를 출력한다

이 과정을 통해서 모든 간격들의 최대 공약수를 구할 수 있다

 

마지막 결과값 출력 부분의 수식의 의미는 다음과 같다

맨 마지막 가로수가 떨어진 위치에서 첫번째 가로수가 떨어진 위치를 빼면 맨 처음부터 맨 끝까지의 거리가 나온다

이는 범위를 구하는 것이다

여기서 tmp (가로수 간격의 최대공약수)를 나누어주면 간격에서 있을 수 있는 모든 가로수가 나오는데, 이 값은 처음 혹은 끝 지점을 포함하지 않는 값이기에 +1 을 해준다

 

그 후 가로수의 개수를 빼주면 심어야 할 가로수의 개수가 나오는 것이다

 

 

고찰

---

# https://www.acmicpc.net/source/62391055

from math import gcd #최대 공약수 찾는 함수

n, *n_list = map(int, open(0).read().split())

#두 지점 사이의 거리
len_n = [j-i for i,j in zip(n_list[:-1],n_list[1:])]

#모든 원소의 최대공약수 한번에 구할 수 있음
g = gcd(*len_n)

#가로수 개수 구하기: 두 나무 사이의 거리를 최대 공약수로 나누고 -1(이미 있으니까)
answer = sum([each//g-1 for each in len_n])
print(answer)

해당 풀이는 다른 분의 코드를 참고하였는데, 이분은 두 지점사이의 거리를 먼저 구하고,

math 라이브러리의 gcd 함수를 사용하여 전체 간격들의 최대공약수를 구하셨다

 

 

참고

---

GitHub - dduneon/CodingTestPy