[python] 백준 - 2485. 가로수

🤔문제 해결

• 수학 - 유클리드호제법 GCD

 

1. 나무들의 간격을 구한다.
2. 간격들의 최대 공약수를 구한다.
3. 간격을 최대공약수로 나누고 1을 빼주면 각각의 간격 사이에 심을 나무의 숫자가 나온다.

 

💻소스 코드

import sys


def gcd_func(a, b):
    while b != 0:
        a, b = b, a % b

    return a


input = sys.stdin.readline
N = int(input())

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

gaps = []
for i in range(1, N):  # 가로수의 간격
    gaps.append(trees[i] - trees[i - 1])

gaps_set = list(set(gaps))  # 간격 중복 제거

gcd = gaps_set[0]
for i in range(1, len(gaps_set)):  # 간격들의 최대공약수
    gcd = gcd_func(gcd, gaps_set[i])

answer_tree_cnt = 0
for gap in gaps:  # 간격을 최대공약수로 나누고 1을 빼주면 심을 나무 숫자
    answer_tree_cnt += gap // gcd - 1

print(answer_tree_cnt)

 

📕문제 확인

출처: BACKJOON ONLINE JUDGE