[python] 백준 2485번

안녕하세요 !

오늘은 백준 - 가로수 문제를 가져왔습니다.

문제 설명

해결 방법

이 문제는 유클리드 호제법으로 최대공약수를 구했습니다. 아래는 최대공약수를 구하는 함수입니다.

def gcd(a, b):
    c = -1
    while 1:
        c = a % b
        if not c:
            return b
        a = b
        b = c

문제를 해결한 방법을 정리해보겠습니다.

1. 입력을 받습니다.
2. 입력받은 가로수 간 차이를 구해주고 그 차이를 정렬합니다.
3. 가로수 간 차이들의 최대공약수(가로수의 간격)를 구해줍니다.
4. 새로 심어야하는 가로수의 개수를 구해줍니다.

1. 입력을 받습니다.

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

2. 입력받은 가로수 간 차이를 구해주고 그 차이를 정렬합니다.

arr2 = []
for i in range(1, len(arr)):
    arr2.append(arr[i] - arr[i-1])
arr2.sort()

3. 가로수 간 차이들의 최대공약수(가로수의 간격)를 구해줍니다.

for i in range(1, len(arr2)):
    arr2[i] = gcd(arr2[i], arr2[i-1])

4. 새로 심어야하는 가로수의 개수를 구해줍니다.

length = arr[-1] - arr[0]
print(length // arr2[-1] + 1 - len(arr))

전체 코드

import sys

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

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

arr2 = []
for i in range(1, len(arr)):
    arr2.append(arr[i] - arr[i-1])

arr2.sort()

def gcd(a, b):
    c = -1
    while 1:
        c = a % b
        if not c:
            return b
        a = b
        b = c

for i in range(1, len(arr2)):
    arr2[i] = gcd(arr2[i], arr2[i-1])

length = arr[-1] - arr[0]
print(length // arr2[-1] + 1 - len(arr))