[Python] 백준 2485 가로수

문제 분석

• 직선 도로
• 일정한 간격이 되도록 가로수를 추가로 심을 때 가장 적은 수의 나무를 심고 싶다.
• 최대한 넓은 간격으로 모든 가로수의 거리가 같도록 하고 싶다.
• 가로수의 위치 : 기준점으로부터 떨어져 있는 거리

 

아이디어 / 코드 설계

• 심어져 있는 나무들 사이 거리 구하기
• 사이 거리들의 최대 공약수
• (거리 // 공약수 -1) 만큼을 다 더 하면 답

 

정답 코드

1차 - 시간초과

import sys
input = sys.stdin.readline

n = int(input())
tree = [int(input()) for _ in range(n)]
interval = []

for i in range(1, len(tree)) :
    interval.append(tree[i] - tree[i-1])

mea = []
maxI = max(interval)
for i in range(2, maxI+1):
    for j in range(len(interval)):
        if interval[j] % i != 0 :
            continue
        mea.append(i)
minM = min(mea)

cnt = 0
for i in range(len(interval)) :
    cnt += interval[i]//minM -1
print(cnt)

 

2차 - 실패..

다른 사람 코드 1

https://velog.io/@aswe0409/%EB%B0%B1%EC%A4%80-2485%EA%B0%80%EB%A1%9C%EC%88%98-%ED%8C%8C%EC%9D%B4%EC%8D%AC

[백준/Python] 2485. 가로수

import sys
input = sys.stdin.readline
import math

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

n = int(input())
cnt = 0

arr = sorted([int(input()) 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 = func_gcd(gcd, sub[i])
    
for j in sub :
    cnt += j//gcd -1

print(cnt)

 

다른 사람 코드 2

def gcd(m, n):
    while n != 0:
        t = m%n
        m = n
        n = t
    return abs(m)

n = int(input())
arr = []
distance = []
for i in range(n):
    arr.append(int(input()))
    if i != 0:
        distance.append(arr[i]-arr[i-1])

# 간격들의 최대공약수를 구한다.
max_gcd = distance[0]
for i in range(n-2):
    max_gcd = gcd(distance[i+1]-distance[i], max_gcd)

# 첫번째 가로수와 마지막 가로수 사이에 필요한 가로수의 수
result = ((arr[n-1]-arr[0])//max_gcd - 1) - n + 2 
print(result)