[백준] 32403 - 전구 주기 맞추기 (python)

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

 

 

상필이는 크리스마스트리 장식에 사용하려고 N$N$개의 전구를 구매했다. 이 전구에 전원을 연결하면 즉시 빛나지 않고 일정한 주기로 반짝인다. 주기가 t$t$초인 전구는 전원을 연결하고 t$t$초, 2×t$2\times t$초, 3×t$3\times t$초, ⋯$\cdots$가 지난 시각에 반짝인다.

상필이는 모든 전구에 전원을 연결하고 T$T$초가 지난 시각에 모든 전구가 동시에 반짝이게 하고 싶다. 상필이는 전구에 전원을 연결하기 전에, N$N$개의 전구 중 하나를 선택해 그 전구의 주기를 1$1$초만큼 늘리거나 줄일 수 있다. 단, 주기를 1$1$초보다 작아지게 할 수는 없다.

전구의 주기를 조절하는 과정을 통해 모든 전구에 전원을 연결하고 T$T$초가 지난 시각에 모든 전구가 동시에 반짝이게 하려면 이 과정을 최소 몇 번 수행해야 하는지 구해보자.

입력

첫째 줄에 전구의 개수 N(1≤N≤1000)$N(1\le N\le 1\, 000)$과 정수 T(1≤T≤1000)$T(1\le T\le 1\, 000)$가 공백으로 구분되어 주어진다.

둘째 줄에 정수 a1,a2,⋯,aN(1≤ai≤1000)$a_1,a_2,\cdots ,a_N(1\le a_i\le 1\, 000)$이 공백으로 구분되어 주어진다. ai$a_i$는 i$i$번째 전구의 주기가 몇 초인지를 의미한다.

출력

모든 전구에 전원을 연결하고 T$T$초가 지난 시각에 모든 전구가 동시에 반짝이게 하려면 이 과정을 최소 몇 번 수행해야 하는지 출력한다.

예제 입력 1 

3 14
4 1 13

예제 출력 1 

3

예제 입력 2 

4 6
2 8 6 3

예제 출력 2 

2

예제 입력 3 

4 12
9 5 3 7

예제 출력 3 

5

 

풀이

import math
from bisect import bisect_left
a, b = map(int, input().split())
t = list(map(int, input().split()))

def find_divisor(n):
    divisors = set()
    for i in range(1, int(math.sqrt(n)) + 1):
        if n % i == 0:
            divisors.add(i)          
            divisors.add(n // i)     
    divisors.add(0)
    divisors.add(math.inf)
    return sorted(divisors)

q = find_divisor(b)
cnt = 0
for i in t :
    idx = bisect_left(q, i)
    cnt += min(abs(i - q[idx]), abs(i - q[idx - 1]))
print(cnt)

 

사실 문제자체는 전구의 개수 N의 입력이 1000까지 밖에 안들어가기 때문에 브루트포스로 하나하나 비교해도 $O(N^2)$로 풀리는데 이분탐색으로 풀게되면 $ O(N \log N) $으로 풀림.

모든 수의 약수는 그 수의 제곱근 까지만 확인해도 알 수 있음.

오랜만에 실버5에 비해 재밌는 문제여서 풀이 남김.