[BOJ 2485] 가로수 (Python)

문제 요약

문제 요약
가로수가 심어져 있는 상태에서 가로수를 최대한 적게 심으면서 모든 가로수가 같은 간격이 되도록 심으려면 몇 그루를 심어야 하는가?
입력
첫째줄 : 심어진 가로수의 수
2 ~ N+1번째 줄 : 심어진 가로수의 위치 (오름차순)
출력
새로 심어야 하는 가로수의 최소수

풀이

모든 가로수가 같은 간격이 되려면 기존 가로수들의 간격들의 공약수인 간격으로 심어야 한다.
그리고 최소로 심으려면 모든 가로수들의 간격의 최대공약수 간격으로 심어야 한다.

그럼 입력받은 가로수들의 위치를 통해 간격을 얻고 최대공약수를 구한 뒤 계산하면 되겠구나!

하지만 입력을 보면 N이 100000까지 가능한 것으로 보아 간격들 중복을 빼는 것이 바람직할 것 같다. (간격이 많을수록 각각의 최대공약수를 구하는 작업이 많아지니까)
그래서 set.add()를 통해 간격들을 모을 것이다.

N = int(input())
dist = set(); prv_num = 0
for i in range(N):
	num = int(input())
    if i != 0:
        dist.add(num - prv_num)
    prv_num = num

이런 식으로 prv_num을 통해 간격을 얻어서 dist라는 집합에 추가할 수 있다.

그럼 최대공약수는 어떻게 얻을까?

최대공약수(GCD)는 유클리드 호제법을 이용해 쉽게 구할 수 있다.

유클리드 호제법

def gcd(a,b):
    while b != 0:
        (a,b)=(b,a%b)
    return a

위 방법으로 dist를 list로 바꾼 뒤 반복문을 통해 GCD를 최신화 시켜주면 GCD를 구할 수 있다.

dist_list = list(dist)
a = dist_list[0]
gcd_num = a
for i in dist_list:
    if i != dist_list[0]:
        gcd_num = gcd(a,i)
        a = gcd_num

최대공약수를 구했는데 몇 개 심을지 어떻게 알아?

예를 들어 입력이 1 3 7 13이라고 하자
간격은 2 4 6이고 이들의 최대공약수는 2이다.
그럼 1과 13 사이에 2 간격으로 몇 그루를 심을 수 있을까?

(마지막 가로수 위치 - 처음 가로수 위치) / (최대공약수) - 1
$(13-1)/2 - 1 = 5$

하지만 여기서 원래 심어져 있던 가로수들을 빼야 한다.

원래 심어져 있던 가로수
전체 가로수 수 - (처음, 마지막 가로수)
$N-2$

처음을 first, 마지막을 last, 최대공약수를 gcd라고 하면 이렇게 식을 세울 수 있다.

$(last-first)/gcd - 1 - (N - 2)$

더 보완해야 할 게 있을까?

• 간격을 dist라는 집합에 넣을 때 first와 last 미리 저장해두기
• dist의 원소가 하나 뿐일 때 생각하기
• 많은 입력이 있으므로 sys.stdin.readline 사용하기

결과 코드

import sys
input = sys.stdin.readline

def gcd(a,b):
    while b != 0:
        (a,b)=(b,a%b)
    return a

N = int(input()); prv_num = first_num = last_num = 0
dist = set()
for i in range(N):
    num = int(input())
    if i == 0:
        first_num = num
    elif i == N-1:
        last_num = num
    
    if i != 0:
        dist.add(num - prv_num)
    
    prv_num = num

dist_list = list(dist)
a = dist_list[0]
gcd_num = a
for i in dist_list:
    if i != dist_list[0]:
        gcd_num = gcd(a,i)
        a = gcd_num

print(int((last_num-first_num)/gcd_num - 1 - (N-2)) if len(dist_list) != 1 else 0)

마치며

비록 수학문제지만 예외처리와 처음 input 부분을 처리하는 것에 신경써야 하는게 좀 어려웠다...