문제
https://www.acmicpc.net/problem/2485
접근
- 모든 가로수의 간격이 같으려면 주어진 가로수의 간격의 최대공약수를 구해야 한다고 생각해서 유클리드 호제법을 이용했다.
- 각 간격을 저장하고 저장된 모든 간격에 대한 최대공약수를 계산한 후, 각 간격을 최대공약수로 나눈 몫 - 1을 합해서 정답을 구한다.
풀이
def gcd(x, y):
if x % y == 0:
return y
return gcd(y, x % y)
n = int(input())
a = [int(input()) for _ in range(n)]
a.sort()
b = []
for i in range(n - 1):
b.append(a[i + 1] - a[i])
div = b[0]
for i in range(len(b) - 1):
div = gcd(b[i + 1], div)
ans = 0
for x in b:
ans += x // div - 1
print(ans)
'Python > Coding Test' 카테고리의 다른 글
21939 문제 추천 시스템 Version 1 (0) | 2022.02.16 |
---|---|
13334 철로 (0) | 2022.02.15 |
19235 모노미노도미노 (0) | 2022.02.13 |
16960 스위치와 램프 (0) | 2022.02.13 |
1781 컵라면 (0) | 2022.02.10 |