[백준] 2485 : 가로수 (Python/파이썬)

문제 링크

https://www.acmicpc.net/problem/2485

문제

직선으로 되어있는 도로의 한 편에 가로수가 임의의 간격으로 심어져있다. 
KOI 시에서는 가로수들이 모두 같은 간격이 되도록 가로수를 추가로 심는 사업을 추진하고 있다. 
KOI 시에서는 예산문제로 가능한 한 가장 적은 수의 나무를 심고 싶다.

편의상 가로수의 위치는 기준점으로 부터 떨어져 있는 거리로 표현되며, 
가로수의 위치는 모두 양의 정수이다.

예를 들어, 가로수가 (1, 3, 7, 13)의 위치에 있다면 (5, 9, 11)의 위치에 가로수를 더 심으면 
모든 가로수들의 간격이 같게 된다. 
또한, 가로수가 (2, 6, 12, 18)에 있다면 (4, 8, 10, 14, 16)에 가로수를 더 심어야 한다.

심어져 있는 가로수의 위치가 주어질 때, 
모든 가로수가 같은 간격이 되도록 새로 심어야 하는 가로수의 최소수를 구하는 프로그램을 작성하라. 
단, 추가되는 나무는 기존의 나무들 사이에만 심을 수 있다.

입력

첫째 줄에는 이미 심어져 있는 가로수의 수를 나타내는 하나의 정수 N이 주어진다(3 ≤ N ≤ 100,000).
둘째 줄부터 N개의 줄에는 각 줄마다 심어져 있는 가로수의 위치가 양의 정수로 주어지며, 
가로수의 위치를 나타내는 정수는 1,000,000,000 이하이다. 
가로수의 위치를 나타내는 정수는 모두 다르고, 
N개의 가로수는 기준점으로부터 떨어진 거리가 가까운 순서대로 주어진다.

출력

모든 가로수가 같은 간격이 되도록 새로 심어야 하는 가로수의 최소수를 첫 번째 줄에 출력한다.

예제

입력

4
1
3
7
13

출력

3

---

정답 및 풀이

import sys

input = sys.stdin.readline

n = int(input())
tree = []
for i in range(n):
    tree.append(int(input()))

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

distance = []
for i in range(len(tree) - 1):
    distance.append(tree[i + 1] - tree[i])

g = distance[0]
for i in range(1, len(distance)):
    g = gcd(g, distance[i])

new_tree = 0
for i in range(len(distance)):
    new_tree += distance[i] // g - 1

print(new_tree)

1. import sys
   • 빠른 입력을 사용하기 위해 sys 모듈을 불러온다.
2. input = sys.stdin.readline
   • input() 대신 더 빠른 입력 방식으로 설정한다.
3. n = int(input())
   • 현재 심어져 있는 나무의 개수를 입력받는다.
4. tree = []
   • 나무들의 위치를 저장할 리스트를 초기화한다.
5. tree.append(int(input()))
   • 각 나무의 위치(좌표)를 입력받아 리스트에 추가한다. (총 n번 실행)
6. def gcd(a, b):
   • 두 수의 최대공약수를 구하는 함수 정의 시작.
7. while b != 0:
   • 유클리드 호제법을 이용하여 b가 0이 될 때까지 반복한다.
8. a, b = b, a % b
   • (a, b)를 (b, a % b)로 갱신하며 최대공약수를 계산한다.
9. return a
   • 최종적으로 계산된 최대공약수를 반환한다.
10. distance = []
    • 나무 사이의 간격(거리)을 저장할 리스트를 초기화한다.
11. distance.append(tree[i + 1] - tree[i])
    • 연속된 두 나무 사이의 거리(간격)를 계산하여 리스트에 추가한다.
12. g = distance[0]
    • 첫 번째 간격을 기준으로 전체 간격들의 GCD를 계산하기 위한 초기값 설정.
13. g = gcd(g, distance[i])
    • 기존 GCD 값과 다음 간격 값을 비교해 새로운 GCD로 갱신한다.
14. new_tree = 0
    • 추가로 심어야 할 나무 개수를 저장하는 변수를 초기화한다.
15. new_tree += distance[i] // g - 1
    • 해당 간격에서 필요한 나무 수를 계산하여 더한다.
    • (간격을 최소 간격 g로 쪼갠 뒤, 이미 있는 1개를 제외)
16. print(new_tree)
    • 모든 간격에서 계산된 추가 나무 수의 총합을 출력한다.

---