백준 파이선 2110 공유기 설치

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

2110번: 공유기 설치

 

입력 부분이 200.000만을 넘기기에 일단 완전탐색을 돌렸다간 시간 초과가 날 것이 뻔했기에

 

이분탐색으로 풀이를 진행했다.

 

다만 start, end, 공유기를 설치할 count를 어디에 설치를 해야할까 고민을 좀 오래 한 것 같은데.

 

start는 리스트의 첫 자리 end는 리스트의 마지막 자리로 정한다음

 

일단 맨 처음자리에 하나(current)는 무조건 설치를 하고

 

for i in range(1,n)으로 current + mid가 arr[i]와 같거나 크다면? 공유기를 설치하고 current는 arr[i]로 변경

 

for i in range(1,n)을 (20만번)을 여러번 돌아가기 떄문에 좀 긴가민가했지만

 

일단 완벽탐색보다는 빠르게 진행되기 떄문에 이 방식을 채택했다.

a,b=map(int,input().split())
li=[int(input()) for _ in range(a)]
li.sort()

def binary_search(array,start,end):
    global answer
    
    while start <= end:
        mid = (start + end) // 2
        current = array[0]
        cnt = 1

        for i in range(1,len(array)):
            if array[i] >= current + mid:
                cnt += 1
                current = array[i]

        if cnt >= b:
            start = mid + 1
            answer = mid
        else:
            end = mid - 1

answer = 0
start = 1
end = li[-1] - li[0]

binary_search(li,start,end)
print(answer)

아 시간초과..

 

그런데 pypy로 제출하니 또 성공한다.

생각해보니 for i in range(n)으로 문자열 li에 숫자를 부여하는 방식인데 20만번을 input으로 처리한다니

당연히 시간초과가 나는게 당연했다.

 

import sys
input = sys.stdin.readline
n,m = map(int,input().split())
li = []
for i in range(n):
    li.append(int(input()))

li.sort()
answer = 0

def binary_search(start,end,arr):
    global answer

    while start <= end:

        cnt = 1
        mid = (start + end) // 2
        corrent = arr[0]

        for i in range(1,n):
            if arr[i] >= corrent + mid:
                cnt += 1
                corrent = arr[i]

        if cnt >= m:
            answer = mid
            start = mid + 1
        else:
            end = mid - 1


start = 0
end = li[-1] - li[0]
binary_search(start,end,li)

print(answer)

이분탐색 너무 어렵다. 어디를 기준으로 잡아야하는지 뭔 20분을 헛고생을 한 기분