[백준/baekjoon] 2485번 가로수 (파이썬)

내 제출

- 종이에 칸 나눠서 나무 위치 표시해보고... 동일 간격을 어떻게 유추해낸 걸까 생각해보니까 어케 어케 풀렸다.

- 처음에 틀린 이유는 굳이 더 심을 필요가 없는 경우(나무 2그루)를 생각 못 했었다.

- math 라이브러리의 gcd 구하는 메소드를 사용해도 될 것 같다. 나는 연습 차원...

- 사실 문제를 이렇게 푸는 건지 긴가민가 해서 코드를 굳이 굳이 길게 작성한 것 같다.

# 최대 공약수 구하기
def get_gcd(a, b):
    while b:
        if a > b:
            a, b = b, a
        b %= a
    return a


# 심어져 있는 가로수의 위치가 주어진다.
# 이미 심어져 있는 가로수의 수 N
n = int(input())

# 가장 첫 번재 나무
front_tree = int(input())

# 나무들 간의 간격 저장
tree_gap = [0] * n

# 심어져 있는 가로수의 위치 입력 받기
for tree_pos in range(1, n):
    tree = int(input())
    # 그 다음 나무는 앞의 나무로부터 얼마나 떨어져 있는지?
    # 1, 3, 7, 13 이면 순서대로 0, 2, 4, 6으로 저장
    tree_gap[tree_pos] = tree - front_tree
    front_tree = tree

gap_gcd = tree_gap[1]

# 간격들의 최대 공약수 찾기
for i in range(1, n):
    gap_gcd = get_gcd(gap_gcd, tree_gap[i])

# 전체 간격 % 최대 공약수 => 나무수
all_gap = sum(tree_gap) // gap_gcd

# 가장 앞 - 뒤 나무 제외, 사이에 있는 나무 수
between_tree = all_gap - 1

print(between_tree - (n-2))

 

결과