[Python] 2485번 : 가로수

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

2485번: 가로수

 

 

문제 3줄 요약

1. 가로수가 임의의 간격을 두며 직선으로 배치 되어있다.

2. 가로수를 더 심어 모든 가로수들의 간격을 같게 한다.

3. 가로수를 최소로 심어 간격을 같게 할 경우, 몇 개 심어야 할까?

 

 

---

그림판을 키고,

그림으로 문제의 이해를 돕도록 하겠다.

 

가로수들의 위치가

한 줄에 하나씩 좌표로 주어진다.

Ex) 1, 3, 7, 13 일 경우

 

위의 그림처럼 표현할 수 있고,

간격이 2, 4, 6 이란 것을 알 수 있다.

 

 

 

그럼 몇 개를 더 심어야 할까?

직관적으로 간격을 봤을 때,

 

 

위 그림처럼 5, 9, 11에 추가를 해주면

간격을 2 씩 두고 있는 가로수를 만들 수 있을 것이다.

 

왜 2 일까?

우린 간격이 2, 4, 6으로 떨어져 있는 가로수를 채워야하고

그렇다면 2, 4, 6을 나눴을 때,

모두 나누어 떨어지는 숫자로 간격을 배치해야하며,

또한 최소 간격인 2보다는 작거나 같아야 할 것이다.

 

만약 2 보다 크다면?

1, 3 가로수 배치부터 실패!

 

 

 

위의 설명한 것을

수학적으로 접근해본다면,

간격의 차이인 2, 4, 6

이 세 정수의 공약수 중 가장 큰

최대공약수인 2가 간격의 최대가 되겠다!

 

from sys import stdin
import math
N = int(stdin.readline())

# tree : 가로수 좌표 리스트
# gap_list : 가로수 간격 리스트
# gcd : 최대공약수
tree, gap_list, gcd = [], [], 0

# 가로수 좌표 리스트
for idx in range(N):
    tree.append(int(stdin.readline()))

# 가로수 좌표가 오름차순이 아닐 수 있으니,
# 오름차순 정렬
tree = sorted(tree)

# 좌표 리스트
# 멀리 있는 가로수 좌표에서 가까운 가로수 좌표를 뺀다.
for idx in range(N):
    if idx != 0:
        gap = tree[idx]-tree[idx-1]
        gap_list.append(gap)

# 간격 차이 중복 제거
set_gap = list(set(gap_list))

# 중복 제거 후,
# 남은 간격 차이가 하나라면, 간격이 동일한 것
if len(set_gap) > 1:
    gcd = math.gcd(set_gap[0], set_gap[1])
    for idx in range(2,len(set_gap)):
        gcd = math.gcd(set_gap[idx], gcd)
    print(sum([distance//gcd-1 for distance in gap_list]))
else:
    print(sum([distance//set_gap[0]-1 for distance in gap_list]))

 

예외 상황인

모두 간격이 같은 경우와

좌표가 오름차순으로 주어지지 않은 경우만 처리해준다면,

 

끝!

 

오늘 그림판 그림 좀 잘그린듯?