문제

문제 접근

동일한 간격으로 나무를 심어줘야 해서 그 도로(배열) 앞의 서로 인접한 값들의 차이를 구하고 그 차이로 나온 값들에서 공통된 가장 큰 약수 즉 최대공약수의 값으로 나무를 심어주면된다

1) 입력 받은 배열의 앞의 요소와 뒤의 요소의 차이를 새로운 배열에 담아준다

2) 최대공약수 구하기
차이를 담은 배열에서 최대공약수를 구한다.

3) 인접한 요소들의 차이를 구해서 차이가 요소들의 몫에서 -1 해주면 나무 심는 갯수가 나온다

문제 풀이

1. 차이 구하기

sub = []
# 1)차이 구하기
for i in range(len(arr) -1):
    sub.append(a
    arr[i+1] - arr[i])

배열을 입력 받을때 정렬을 진행해서 뒤의 요소가 앞의 요소보다 크다.

2. 최대 공약수 구하기

import math
print(math.gcd(*sub))

파이썬 math에서 최대공약수 구하는 함수인 gcd로 쉽게 구할수 있는 방법과

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

유클리드 호제법을 이용한 방법이 있다.

유클리드 호제법

숫자 a, b가 있을 때, a를b로 나눈 나머지(x)와
b의 최대공약수는 a와 b의 최대공약수가 같다 (a> b)

=> a를 b로 나눈 나머지 = b의 최대 공약수

계속해서 a를 b로 나누어서 b를 a에 나눈 나머지를 b에 대입시켜서 b가 0이 될때 까지 반복하면 남는 값이 최대공약수이다.

나무 심기

for j in sub:
    cnt += j // gcd -1

인접한 요소들의 차이를 구해서 차이가 요소들의 몫에서 -1 해주면 나무 심는 갯수가 나온다

최종 코드

import sys
import math
def f_gcd(a,b):
    while b > 0:
        a,b = b,a % b
    return a

n = int(input())
cnt = 0

arr = sorted([int(sys.stdin.readline()) for _ in range(n)])

sub = []
# 1)차이 구하기
for i in range(len(arr) -1):
    sub.append(arr[i+1] - arr[i])

#2) 최대공약수 구하기
gcd = sub[0]
for i in range(1, len(sub)):
    gcd = f_gcd(gcd, sub[i])
    
    
for j in sub:
    cnt += j // gcd -1
        
print(cnt)

문제 링크

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