파이썬 가로수(백준 BOJ 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 이하이다. 가로수의 위치를 나타내는 정수는 모두 다르다.
출력
모든 가로수가 같은 간격이 되도록 새로 심어야 하는 가로수의 최소수를 첫 번째 줄에 출력한다.
예제 입력 1
4
1
3
7
13
예제 출력 1
3
예제 입력 2
4
2
6
12
18
예제 출력 2
5
📝풀어보기
📌 심어진 가로수 수 N을 입력받는다.
다음으로 첫번째 가로수를 입력받고 배열을 하나 만들어 첫번째 입력한 가로수의 개수를 제외한(N-1) 범위에서 다음 가로수를 입력받는다.
배열에 2번째 입력된 가로수 n에서 이전 입력값 a를 뺀 값을 저장하고 a를 n의 값으로 갱신한다.
import sys
def GCD(A, B):
while B != 0:
tmp = A % B
A = B
B = tmp
return A
# 가로수의 간격
N = int(sys.stdin.readline())
# 첫번째 가로수
a = int(sys.stdin.readline())
# 가로수 사이의 값 저장
arr = []
# 첫번째 입력을 제외하고 끝까지 돌면서
for i in range(N-1):
n = int(sys.stdin.readline())
# 2번째 입력부터 이전 입력값을 뺀것을 저장
arr.append(n - a)
a = n
📌 g에 배열의 첫번 째 값을 저장한다(최대공약수를 계산하기 위함)
배열의 1번째 인덱스부터 배열 끝까지 돌면서 배열안의 모든 수들의 최대공약수를 찾는다.
두 가로수 사이에 심을 가로수의 개수는 간격을 배열 내 모든수의 최대공약수 -1로 나눈 몫이다.
# arr에 들어있는 모든 수들의 최대공약수 찾기
g = arr[0]
for j in range(1, len(arr)):
g = GCD(g, arr[j])
# 두 가로수 사이에 심을 가로수의 개수는 간격 // 최대공약수 -1
res = 0
for k in arr:
res += k // g-1
print(res)
전체코드
import sys
def GCD(A, B):
while B != 0:
tmp = A % B
A = B
B = tmp
return A
# 가로수의 간격
N = int(sys.stdin.readline())
# 첫번째 가로수
a = int(sys.stdin.readline())
# 가로수 사이의 값 저장
arr = []
# 첫번째 입력을 제외하고 끝까지 돌면서
for i in range(N-1):
n = int(sys.stdin.readline())
# 2번째 입력부터 이전 입력값을 뺀것을 저장
arr.append(n - a)
a = n
# arr에 들어있는 모든 수들의 최대공약수 찾기
g = arr[0]
for j in range(1, len(arr)):
g = GCD(g, arr[j])
# 두 가로수 사이에 심을 가로수의 개수는 간격 // 최대공약수 -1
res = 0
for k in arr:
res += k // g-1
print(res)