[백준] 2486번 가로수(python)

마뇽미뇽·2025년 7월 3일
0

알고리즘 문제풀이

목록 보기
143/165

1. 문제

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

2. 풀이

  • 나무 사이의 공간이 최대공약수임으로 두 배열사이의 차이와 최대공약수를 구한다.
  • 2 ~ 18까지라고 가정하면 2,4,6,8,10,12,14,16,18임으로 2와 18사이에 나무를 심는 것이기 때문에 사이값을 확인하기 위해 각 배열의 끝 값을 뺸 후 차이만큼 나눈다.
  • 그 후 이미 입력받은 값인 n개의 나무가 존재하기에 간격은 n-개가 있으므로 n-1개 만큼 제거한다.

3. 코드

최종 코드

import math
import sys

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

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

diff = tree[1] - tree[0]
for i in range(2,len(tree)):
    diff = math.gcd(diff, tree[i] - tree[i - 1])

print((tree[-1] - tree[0]) // diff - (n - 1))

이전 코드(메모리초과)

import math
import sys

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

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

diff = 100000
for i in range(1,len(tree)):
    temp = abs(tree[i-1] - tree[i])
    if temp < diff:
        diff = temp

for i in tree:
    temp = diff
    gcd = math.gcd(temp, i)

    if gcd != 1 and diff > gcd:
        diff = gcd

ans = set(i for i in range(tree[0],tree[-1] + 1,diff))
tree = set(tree)
print(len(ans - tree))

이전에는 배열 전체를 돌린 후 set을 이용한 차집합을 활용해 남은 집합의 갯수를 통해 구현하였다.

profile
Que sera, sera

0개의 댓글