가로수1

• 백준 알고리즘 2485번: 가로수 (Python) 문제 정보 2485번: 가로수 첫째 줄에는 이미 심어져 있는 가로수의 수를 나타내는 하나의 정수 N이 주어진다(3 ≤ N ≤ 100,000). 둘째 줄부터 N개의 줄에는 각 줄마다 심어져 있는 가로수의 위치가 양의 정수로 주어지며, 가 www.acmicpc.net 핵심 최대공약수 문제다! 라는 것을 빠르게 캐치하여야 함 일일히 최대공약수를 구하는것은 정말 비효율적이니, 유클리드 호제법을 통해서 구하는 것이 올바른 풀이이다 각 가로수의 간격들의 전체 최대공약수를 구하고 이 간격에서 비어있는 가로수의 개수를 찾아서 출력해주면 된다 풀이 from sys import stdin N = int(stdin.readline()) tree = list(map(int, stdin.readlines())) def GCD(.. 알고리즘/Python 2023. 6. 29.