백준 가로수 2485(실버4) PYTHON

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

 

import math
from functools import reduce
def gcd_multiple(list):
    return reduce(math.gcd,list)
n = int(input())
answer = []
check = []
number = []
for i in range(n):
    k = int(input())
    answer.append(k)
for i in range(len(answer)-1):
    check.append(answer[i+1]-answer[i])

result = gcd_multiple(check)
total = (answer[-1] - answer[0])//result+1
print(total-len(answer))

사실 문제를 처음보고 난 생각의 떨어져있는 간격들을 전부 구해준뒤,구한값들의 최대공약수가 구간의 합이라고 생각했다.

하지만 모든 간격들의 최대공약수를 구하는데 어려움이 있었다. 파이썬 모듈중 functools에있는 reduce가 있다는것을 배웠다.

reduce 함수는 주어진 함수와 iterable(반복 가능한 객체, 예: 리스트)을 이용해 하나의 결과를 반환하는 데 사용됩니다.

그래서 간격의 모든값들을 list에 넣어준뒤 reduce함수를 사용하여 간격의 모든값들의 최대 공약수를 구하여주었다.

그리고 마지막에 개수를 세는 과정에서 모든값들을 list에 넣어서 len을 통해 비교하려 했지만, 그렇게 하니 메모리 초과가 나왔다.

변수 하나를 만들어서 입력된 값의 초기값과 마지막값을 뺴준뒤 구한 최대공약수로 나뉘어주어서 총 몇개의 개수가 나왔는지 알수있었다.