파이썬 알고리즘 235번 | [백준 2485번] 가로수 - GCD (최대공약수)

235. 가로수

1) 어떤 전략(알고리즘)으로 해결?

2) 코딩 설명

• 나무들 간격들을 모두 모아놓고, 이 간격들의 최대공약수가 간격이 된다!
• 거리//최대공약수 => 필요한 전체 나무 갯수
• 여기서 이미 있는 나무 갯수 빼주면 되지
  https://yuuj.tistory.com/121 분의 설명을 보고 문제 이해 !

<내 풀이>

import sys
import math

n = int(sys.stdin.readline().rstrip())

# 나무들 모아
tree = []
for _ in range(n) :
    tree.append(int(sys.stdin.readline().rstrip()))
tree.sort()

# 간격 모아 모아 
interval_lis = []
for t in range(1,n) :
        interval_lis.append(tree[t]-tree[t-1])
        
# 이 간격들의 최대공약수
gcdd = interval_lis[0]
for n in range(len(interval_lis)) :
    gcdd = math.gcd(interval_lis[n], gcdd)
# print(gcdd)
# 필요한 나무의 갯수 =
# 전체 나무 갯수(간격으로 했을시) - 기존 주어진나무갯수

total_tree_num = (tree[-1]-tree[0])//gcdd+1
print(total_tree_num-len(tree))

<내 틀렸던 풀이, 문제점>

- 요상하게 접근했었음,,

• 무작정 가장 작은 간격을 찾으면 될 것이라 생각했었다 ;;

import sys

n = int(sys.stdin.readline().rstrip())
tree = []
for _ in range(n) :
    tree.append(int(sys.stdin.readline().rstrip()))

tree.sort()

interval = 10000000001

for t in range(1,n) :
    if tree[t]-tree[t-1] < interval : 
        interval = tree[t]-tree[t-1]

new = [0 for _ in range(max(tree))]
#print(new)
add_tree = 0
for i in range(1,max(tree)+1,interval) : 
    #print(i)
    if i not in tree :
        add_tree+=1

print(add_tree)

<반성 점>

<배운 점>