백준-2485-가로수(파이썬)

문제이해

• 심어져 있는 가로수의 위치가 주어진다.
• 모든 가로수가 같은 간격이 되도록 새로 심어야 하는 가로수의 최소수를 구한다.

문제생각

• 일단 오름차순 정렬을 한 뒤 최소간격을 구한다.
• 최소간격으로부터 1씩 줄여가며 모든 간격에서 나눠 떨어지는지 확인한다.
• 이 경우 제일 먼저 나눠떨어지는 값이 간격이 되며 이때의 개수를 구하면된다.

문제풀이

위의 코드는 시간초과가뜬 코드이다.
모든 간격에서 제일 먼저 나눠떨어진다는 의미는 최대공약수라는 의미였다.
파이썬의 gcd 함수를 사용하면 풀릴 것 같다.

위의 코드는 모든 경우에서 반복문을 돌린 처음의 코드에서 유클리드 호제법을 이용한 최대공약수를 구하여 해결한 코드이다.